From the 1 of 10 linked papers with an AI index.
7 papers · 1 filter
Online Correlation Clustering with Metric Weights
Sami Davies, Benjamin Moseley, Heather Newman
The standard online version of correlation clustering is prohibitively hard, as even randomized algorithms cannot achieve competitive ratio better than . Prior works bypass t…
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…
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…
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…
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…