4 papers
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…
No, Cake Cutting Really is a Piece of Cake
Stephen Arndt, Benjamin Moseley, Sungjin Im +1
We design and analyze a deterministic cake cutting algorithm that achieves proportional fairness using a linear number of cuts. The best previous upper bound on the number of cuts…
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…