From the 1 of 12 linked papers with an AI index.
10 papers · 1 filter
Efficiently Coloring the Intersection of a General Matroid and Combinatorial Matroids
Stephen Arndt, Benjamin Moseley, Kirk Pruhs +1
The paper presents a polynomial‑time algorithm that colors the intersection of a general matroid with several partition (or related combinatorial) matroids using at most a constant…
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…
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…
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…