Travelled to:1 × Denmark
1 × France
1 × Switzerland
7 × USA
Collaborated with:Y.Makarychev M.Charikar M.Sviridenko A.Vijayaraghavan D.Panigrahi A.Ghoting G.Yaroslavtsev R.Manokaran S.Chawla T.Schramm A.Agarwal N.Alon A.Naor P.Berman A.Bhattacharyya S.Raskhodnikova
Talks about:algorithm (5) approxim (5) problem (4) partit (3) graph (3) cut (3) quadrat (2) maximum (2) complet (2) direct (2)
Person: Konstantin Makarychev
DBLP: Makarychev:Konstantin
Contributed to:
2015
20142014201220112010
2009200920062005Wrote 13 papers:
- STOC-2015-ChawlaMSY #algorithm #clustering #graph
- Near Optimal LP Rounding Algorithm for CorrelationClustering on Complete and Complete k-partite Graphs (SC, KM, TS, GY), pp. 219–228.
- ICALP-v1-2014-MakarychevM #clustering #graph
- Nonuniform Graph Partitioning with Unrelated Weights (KM, YM), pp. 812–822.
- ICALP-v1-2014-MakarychevP #scheduling
- Precedence-Constrained Scheduling of Malleable Jobs with Preemption (KM, DP), pp. 823–834.
- STOC-2014-MakarychevMV #approximate #constant
- Constant factor approximation for balanced cut in the PIE model (KM, YM, AV), pp. 41–49.
- STOC-2012-MakarychevMV #algorithm #approximate #clustering #problem
- Approximation algorithms for semi-random partitioning problems (KM, YM, AV), pp. 367–384.
- ICALP-v1-2011-BermanBMRY #approximate #problem
- Improved Approximation for the Directed Spanner Problem (PB, AB, KM, SR, GY), pp. 1–12.
- ICALP-v1-2011-MakarychevS #constraints
- Maximizing Polynomials Subject to Assignment Constraints (KM, MS), pp. 510–520.
- ICALP-v1-2010-MakarychevMS #algorithm #approximate #polynomial #problem #reduction
- Maximum Quadratic Assignment Problem: Reduction from Maximum Label Cover and LP-Based Approximation Algorithm (KM, RM, MS), pp. 594–604.
- SIGMOD-2009-GhotingM #parallel #performance
- Serial and parallel methods for i/o efficient suffix tree construction (AG, KM), pp. 827–840.
- STOC-2009-CharikarMM
- Integrality gaps for Sherali-Adams relaxations (MC, KM, YM), pp. 283–292.
- STOC-2006-CharikarMM #algorithm #game studies
- Near-optimal algorithms for unique games (MC, KM, YM), pp. 205–214.
- STOC-2005-AgarwalCMM #algorithm #approximate #problem
- O(sqrt(log n)) approximation algorithms for min UnCut, min 2CNF deletion, and directed cut problems (AA, MC, KM, YM), pp. 573–581.
- STOC-2005-AlonMMN #graph #polynomial
- Quadratic forms on graphs (NA, KM, YM, AN), pp. 486–493.