21 citations · 94 across the 25 of their papers we have counts for
4 papers · 1 filter
Near Optimal LP Rounding Algorithm for Correlation Clustering on Complete and Complete k-partite Graphs
Shuchi Chawla, Konstantin Makarychev, Tselil Schramm +1
We give new rounding schemes for the standard linear programming relaxation of the correlation clustering problem, achieving approximation factors almost matching the integrality g…
Going for Speed: Sublinear Algorithms for Dense r-CSPs
Grigory Yaroslavtsev
We give new sublinear and parallel algorithms for the extensively studied problem of approximating n-variable r-CSPs (constraint satisfaction problems with constraints of arity r u…
Online Algorithms for Machine Minimization
Nikhil Devanur, Konstantin Makarychev, Debmalya Panigrahi +1
In this paper, we consider the online version of the machine minimization problem (introduced by Chuzhoy et al., FOCS 2004), where the goal is to schedule a set of jobs with releas…
Parallel Algorithms for Geometric Graph Problems
Alexandr Andoni, Aleksandar Nikolov, Krzysztof Onak +1
We give algorithms for geometric graph problems in the modern parallel models inspired by MapReduce. For example, for the Minimum Spanning Tree (MST) problem over a set of points i…