7 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…
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…
Efficiently Coloring the Intersection of a General Matroid and Combinatorial Matroids
Stephen Arndt, Benjamin Moseley, Kirk Pruhs +1
This paper shows a polynomial-time algorithm that, given a general matroid and partition matroids , produces a coloring of the intersection $M = \cap…
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…
An -Competitive Posted-Price Algorithm for Online Matching on the Line
Stephen Arndt, Josh Ascher, Kirk Pruhs
Motivated by demand-responsive parking pricing systems, we consider posted-price algorithms for the online metric matching problem. We give an -competitive posted-price…