3 citations · 4 across the 9 of their papers we have counts for
10 papers
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…
Online Correlation Clustering: Simultaneously Optimizing All -norms
Sami Davies, Benjamin Moseley, Heather Newman
The -norm objectives for correlation clustering present a fundamental trade-off between minimizing total disagreements (the -norm) and ensuring fairness to individu…
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…
Robust Gittins for Stochastic Scheduling
Benjamin Moseley, Heather Newman, Kirk Pruhs +1
A common theme in stochastic optimization problems is that, theoretically, stochastic algorithms need to "know" relatively rich information about the underlying distributions. This…
Efficient Algorithms for Cardinality Estimation and Conjunctive Query Evaluation With Simple Degree Constraints
Sungjin Im, Benjamin Moseley, Hung Q. Ngo +1
Cardinality estimation and conjunctive query evaluation are two of the most fundamental problems in database query processing. Recent work proposed, studied, and implemented a robu…
Asymptotically Optimal Scheduling of Multiple Parallelizable Job Classes
Benjamin Berg, Benjamin Moseley, Weina Wang +1
Modern computing workloads are often composed of parallelizable jobs. A parallelizable job can be completed more quickly when run on additional servers. However, each job can only…