7 citations · 9 across the 3 of their papers we have counts for
7 papers · 1 filter
Scheduling Problems with Constrained Rejections
Sami Davies, Venkatesan Guruswami, Xuandi Ren
We study bicriteria versions of Makespan Minimization on Unrelated Machines and Santa Claus by allowing a constrained number of rejections. Given an instance of Makespan Minimizati…
Warm-starting Push-Relabel
Sami Davies, Sergei Vassilvitskii, Yuyan Wang
Push-Relabel is one of the most celebrated network flow algorithms. Maintaining a pre-flow that saturates a cut, it enjoys better theoretical and empirical running time than other…
Online Flexible Busy Time Scheduling on Heterogeneous Machines
Gruia Calinescu, Sami Davies, Samir Khuller +1
We study the online busy time scheduling model on heterogeneous machines. In our setting, jobs with uniform length arrive online with a deadline that becomes known to the algorithm…
Simultaneously Approximating All -norms in Correlation Clustering
Sami Davies, Benjamin Moseley, Heather Newman
This paper considers correlation clustering on unweighted complete graphs. We give a combinatorial algorithm that returns a single clustering solution that is simultaneously …
On the Hardness of Scheduling With Non-Uniform Communication Delays
Sami Davies, Janardhan Kulkarni, Thomas Rothvoss +3
In the scheduling with non-uniform communication delay problem, the input is a set of jobs with precedence constraints. Associated with every precedence constraint between a pair o…
Approximate Trace Reconstruction
Sami Davies, Miklos Z. Racz, Cyrus Rashtchian +1
In the usual trace reconstruction problem, the goal is to exactly reconstruct an unknown string of length after it passes through a deletion channel many times independently, p…