From the 1 of 6 linked papers with an AI index.
5 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…
Competitive Online Transportation Simplified
Stephen Arndt, Benjamin Moseley, Kirk Pruhs +1
The setting for the online transportation problem is a metric space , populated by parking garages of varying capacities. Over time cars arrive in , and must be irrevocab…