3 citations · 4 across the 9 of their papers we have counts for
4 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…
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…