7 citations · 15 across the 11 of their papers we have counts for
14 papers
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, Adrian Calinescu, Sami Davies +2
We study the online busy time scheduling model on heterogeneous machines. In our setting, jobs with uniform processing time arrive online with a deadline that becomes known to the…
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 …
Predictive Flows for Faster Ford-Fulkerson
Sami Davies, Benjamin Moseley, Sergei Vassilvitskii +1
Recent work has shown that leveraging learned predictions can improve the running time of algorithms for bipartite matching and similar combinatorial problems. In this work, we bui…
Fast Combinatorial Algorithms for Min Max Correlation Clustering
Sami Davies, Benjamin Moseley, Heather Newman
We introduce fast algorithms for correlation clustering with respect to the Min Max objective that provide constant factor approximations on complete graphs. Our algorithms are the…
Robust Factorizations and Colorings of Tensor Graphs
Joshua Brakensiek, Sami Davies
Since the seminal result of Karger, Motwani, and Sudan, algorithms for approximate 3-coloring have primarily centered around SDP-based rounding. However, it is likely that importan…
Balancing Flow Time and Energy Consumption
Sami Davies, Samir Khuller, Shirley Zhang
In this paper, we study the following batch scheduling model: find a schedule that minimizes total flow time for uniform length jobs, with release times and deadlines, where th…
Lower Bounds on the Total Variation Distance Between Mixtures of Two Gaussians
Sami Davies, Arya Mazumdar, Soumyabrata Pal +1
Mixtures of high dimensional Gaussian distributions have been studied extensively in statistics and learning theory. While the total variation distance appears naturally in the sam…
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…
Scheduling with Communication Delays via LP Hierarchies and Clustering
Sami Davies, Janardhan Kulkarni, Thomas Rothvoss +2
We consider the classic problem of scheduling jobs with precedence constraints on identical machines to minimize makespan, in the presence of communication delays. In this setting,…
Reconstructing Trees from Traces
Sami Davies, Miklos Z. Racz, Cyrus Rashtchian
We study the problem of learning a node-labeled tree given independent traces from an appropriately defined deletion channel. This problem, tree trace reconstruction, generalizes s…
A Tale of Santa Claus, Hypergraphs and Matroids
Sami Davies, Thomas Rothvoss, Yihao Zhang
A well-known problem in scheduling and approximation algorithms is the Santa Claus problem. Suppose that Santa Claus has a set of gifts, and he wants to distribute them among a set…