6 citations · 25 across the 31 of their papers we have counts for
32 papers · 1 filter
Optimal Convergence of Iterative Methods for Datalogo
Simon Frisk, Sungjin Im, Paraschos Koutris +4
has been introduced as an extension to Datalog that increases expressiveness, yet retains simple least fixpoint semantics and admits optimization technique…
Matroid Contention Resolution with Concentration
Stephen Arndt, Benjamin Moseley, Kirk Pruhs +1
Contention resolution schemes (CRS) are a fundamental and widely applied tool for rounding fractional solutions subject to combinatorial constraints. However, the known analyses of…
An Randomized Lower Bound for Cutting a Cake into Proportionally Fair Pieces
Stephen Arndt, Kirk Pruhs, Trung Tran
We consider the classic cake cutting problem in the Robertson-Webb model, with the objective of proportional fairness. We show that any randomized algorithm must use …
Approximation Algorithms for Matroid-Intersection Coloring with Applications to Rota's Basis Conjecture
Stephen Arndt, Benjamin Moseley, Kirk Pruhs +2
We study algorithmic matroid intersection coloring. Given matroids on a common ground set of elements, the goal is to partition into the fewest number of color clas…
Minimizing Completion Times of Stochastic Jobs on Parallel Machines is Hard
Benjamin Moseley, Kirk Pruhs, Marc Uetz +1
This paper considers the scheduling of stochastic jobs on parallel identical machines to minimize the expected total weighted completion time. While this is a classical problem wit…
Indirect Coflow Scheduling
Alexander Lindermayr, Kirk Pruhs, Andréa W. Richa +1
We consider routing in reconfigurable networks, which is also known as coflow scheduling in the literature. The algorithmic literature generally (perhaps implicitly) assumes that t…