23 citations · 146 across the 41 of their papers we have counts for
8 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…
Constant Factor Approximation for Balanced Cut in the PIE model
Konstantin Makarychev, Yury Makarychev, Aravindan Vijayaraghavan
We propose and study a new semi-random semi-adversarial model for Balanced Cut, a planted model with permutation-invariant random edges (PIE). Our model is much more general than p…
Correlation Clustering with Noisy Partial Information
Konstantin Makarychev, Yury Makarychev, Aravindan Vijayaraghavan
In this paper, we propose and study a semi-random model for the Correlation Clustering problem on arbitrary graphs G. We give two approximation algorithms for Correlation Clusterin…
Precedence-constrained Scheduling of Malleable Jobs with Preemption
Konstantin Makarychev, Debmalya Panigrahi
Scheduling jobs with precedence constraints on a set of identical machines to minimize the total processing time (makespan) is a fundamental problem in combinatorial optimization.…
Optimization Problems with Diseconomies of Scale via Decoupling
Konstantin Makarychev, Maxim Sviridenko
We present a new framework for solving optimization problems with a diseconomy of scale. In such problems, our goal is to minimize the cost of resources used to perform a certain t…
Maximum Quadratic Assignment Problem: Reduction from Maximum Label Cover and LP-based Approximation Algorithm
Konstantin Makarychev, Rajsekar Manokaran, Maxim Sviridenko
We show that for every positive , unless NP BPQP, it is impossible to approximate the maximum quadratic assignment problem within a factor better than $2^{\log^{1-ε…