4 papers · 1 filter
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…
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…