KM
Konstantin Makarychev
cs.DScs.LGcs.CCcs.ITmath.COmath.ITmath.PRAlgorithmsbioengineeringComputers, Mainframe
On Valency
published · living versionsW_qrnha7w5·v1 · currentpublished
A bi-criteria approximation algorithm for Means
with Yury Makarychev, Maxim Sviridenko, Justin Ward
1 version
Preprints & journals
50 papers in the corpus · 2007–2026On the Approximability of Max-Cut on 3-Colorable Graphs and Graphs with Large Independent Sets2604.10318v1 · Suprovat Ghoshal, Neng Huang, Euiwoong Lee et al.2026 · 0 citationsarXiv
A Simple Average-case Analysis of Recursive Randomized Greedy MIS2604.01462v1 · Mina Dalirrooyfard, Konstantin Makarychev, Slobodan Mitrovi'c2026 · 0 citationsarXiv
Dynamic Algorithm for Explainable k-medians Clustering under lp Norm2512.01150v1 · Konstantin Makarychev, Ilias Papanikolaou, Liren Shan2025 · 0 citationsarXiv
SPARSE-PIVOT: Dynamic correlation clustering for node insertions2507.01830v1 · Mina Dalirrooyfard, Konstantin Makarychev, Slobodan Mitrovi'c2025 · 0 citationsarXiv
Constraint Satisfaction Problems with Advice2403.02212v2 · Suprovat Ghoshal, Konstantin Makarychev, Yury Makarychev2024 · 0 citationsarXiv
Pruned Pivot: Correlation Clustering Algorithm for Dynamic, Parallel, and Local Computation Models2402.15668v2 · Mina Dalirrooyfard, Konstantin Makarychev, Slobodan Mitrovi'c2024 · 0 citationsarXiv
Higher-Order Cheeger Inequality for Partitioning with Buffers2308.10160v1 · Konstantin Makarychev, Yury Makarychev, Liren Shan et al.2023 · 0 citationsarXiv
Approximation Algorithms for Norm Multiway Cut2308.08373v1 · Charlie Carlson, Jafar Jafarov, Konstantin Makarychev et al.2023 · 0 citationsarXiv
Random Cuts are Optimal for Explainable k-Medians2304.09113v1 · Konstantin Makarychev, Liren Shan2023 · 2 citationsarXiv
Triplet Reconstruction and all other Phylogenetic CSPs are Approximation Resistant2212.12765v2 · Vaggos Chatziafratis, Konstantin Makarychev2022 · 2 citationsarXiv
Explainable k-means. Don't be greedy, plant bigger trees!2111.03193v2 · Konstantin Makarychev, Liren Shan2021 · 10 citationsarXiv
Correlation Clustering with Asymmetric Classification Errors2108.05696v1 · Jafar Jafarov, Sanchit Kalhan, Konstantin Makarychev et al.2021 · 2 citationsarXiv
Local Correlation Clustering with Asymmetric Classification Errors2108.05697v1 · Jafar Jafarov, Sanchit Kalhan, Konstantin Makarychev et al.2021 · 3 citationsarXiv
Near-optimal Algorithms for Explainable k-Medians and k-Means2107.00798v2 · Konstantin Makarychev, Liren Shan2021 · 12 citationsarXiv
Batch Optimization for DNA Synthesis2011.14532v2 · Konstantin Makarychev, Miklos Z. Racz, Cyrus Rashtchian et al.2020 · 16 citationsarXiv
Improved Guarantees for k-means++ and k-means++ Parallel2010.14487v1 · Konstantin Makarychev, Aravind Reddy, Liren Shan2020 · 8 citationsNeurIPS 2020
Performance of Johnson-Lindenstrauss Transform for k-Means and k-Medians Clustering1811.03195v2 · Konstantin Makarychev, Yury Makarychev, Ilya Razenshteyn2018 · 74 citationsarXiv
Bisect and Conquer: Hierarchical Clustering via Max-Uncut Bisection1912.06983v1 · Sara Ahmadian, Vaggos Chatziafratis, Alessandro Epasto et al.2019 · 4 citationsarXiv
Erratum: Random access in large-scale DNA data storage.29979658 · Organick, Lee, Ang, Siena Dumas, Chen, Yuan-Jyue et al.2019 · 10 citationsNature biotechnology. 2018;36(7):660
DNA assembly for nanopore data storage readout.31270330 · Lopez, Randolph, Chen, Yuan-Jyue, Dumas Ang, Siena et al.2019 · 147 citationsNature communications. 2019;10(1):2933
Improved algorithms for Correlation Clustering with local objectives1902.10829v2 · Sanchit Kalhan, Konstantin Makarychev, Timothy Zhou2019 · 2 citationsarXiv
Random access in large-scale DNA data storage.29457795 · Organick, Lee, Ang, Siena Dumas, Chen, Yuan-Jyue et al.2018 · 784 citationsNature biotechnology. 2018;36(3):242-248
Robust algorithms with polynomial loss for near-unanimity CSPs1607.04787v4 · V'ictor Dalmau, Marcin Kozik, Andrei Krokhin et al.2016 · 7 citationsarXiv
Nonlinear Dimension Reduction via Outer Bi-Lipschitz Extensions1811.03591v1 · Sepideh Mahabadi, Konstantin Makarychev, Yury Makarychev et al.2018 · 27 citationsarXiv
Scaling up DNA data storage and randomaccess retrieval10.1101/114553v1 · Organick, L., Ang, S. D., Chen, Y.-J. et al.2017 · 31 citationsbioRxiv
Metric Perturbation Resilience1607.06442v1 · Konstantin Makarychev, Yury Makarychev2016 · 1 citationarXiv
Learning Communities in the Presence of Errors1511.03229v3 · Konstantin Makarychev, Yury Makarychev, Aravindan Vijayaraghavan2015 · 20 citationsarXiv
Satisfiability of Ordering CSPs Above Average1503.03851v2 · Konstantin Makarychev, Yury Makarychev, Yuan Zhou2015 · 0 citationsarXiv
A bi-criteria approximation algorithm for $k$ Means1507.04227v2 · Konstantin Makarychev, Yury Makarychev, Maxim Sviridenko et al.2015 · 27 citationsarXivon Valency
Near Optimal LP Rounding Algorithm for Correlation Clustering on Complete and Complete k-partite Graphs1412.0681v3 · Shuchi Chawla, Konstantin Makarychev, Tselil Schramm et al.2014 · 3 citationsarXiv
Correlation Clustering with Noisy Partial Information1406.5667v2 · Konstantin Makarychev, Yury Makarychev, Aravindan Vijayaraghavan2014 · 5 citationsarXiv
Optimization Problems with Diseconomies of Scale via Decoupling1404.3248v2 · Konstantin Makarychev, Maxim Sviridenko2014 · 0 citationsarXiv
Constant Factor Approximation for Balanced Cut in the PIE model1406.5665v1 · Konstantin Makarychev, Yury Makarychev, Aravindan Vijayaraghavan2014 · 18 citationsarXiv
Nonuniform Graph Partitioning with Unrelated Weights1401.0699v3 · Konstantin Makarychev, Yury Makarychev2014 · 1 citationarXiv
Precedence-constrained Scheduling of Malleable Jobs with Preemption1404.6850v1 · Konstantin Makarychev, Debmalya Panigrahi2014 · 14 citationsarXiv
Maximum Quadratic Assignment Problem: Reduction from Maximum Label Cover and LP-based Approximation Algorithm1403.7721v1 · Konstantin Makarychev, Rajsekar Manokaran, Maxim Sviridenko2014 · 28 citationsarXiv
Online Algorithms for Machine Minimization1403.0486v2 · Nikhil Devanur, Konstantin Makarychev, Debmalya Panigrahi et al.2014 · 8 citationsarXiv
Bilu-Linial Stable Instances of Max Cut and Minimum Multiway Cut1305.1681v3 · Konstantin Makarychev, Yury Makarychev, Aravindan Vijayaraghavan2013 · 32 citationsarXiv
Approximation Algorithm for Sparsest k-Partitioning1306.4384v2 · Anand Louis, Konstantin Makarychev2013 · 14 citationsarXiv
Local Search is Better than Random Assignment for Bounded Occurrence Ordering k-CSPs1210.1890v2 · Konstantin Makarychev2012 · 4 citationsarXiv
Approximation Algorithm for Non-Boolean MAX k-CSP1206.3603v1 · Konstantin Makarychev, Yury Makarychev2012 · 6 citationsarXiv
Design of multiple sequence alignment algorithms on parallel, distributed memory supercomputers.22254462 · Church, Philip C, Goscinski, Andrzej, Holt, Kathryn et al.2012 · 14 citationsAnnual International Conference of the IEEE Engineering in Medicine and Biology Society. IEEE Engineering in Medicine and Biology Society. Annual International Conference. 2011;2011:924-7
Min-Max Graph Partitioning and Small Set Expansion1110.4319v2 · Nikhil Bansal, Uriel Feige, Robert Krauthgamer et al.2011 · 47 citationsarXiv
The Grothendieck constant is strictly smaller than Krivine's bound1103.6161v3 · Mark Braverman, Konstantin Makarychev, Yury Makarychev et al.2011 · 62 citationsarXiv
How to Play Unique Games against a Semi-Random Adversary1104.3806v1 · Alexandra Kolla, Konstantin Makarychev, Yury Makarychev2011 · 4 citationsarXiv
On Parsimonious Explanations for 2-D Tree- and Linearly-Ordered Data1101.1941v1 · Howard Karloff, Flip Korn, Konstantin Makarychev et al.2011 · 6 citationsarXiv
Improved Approximation for the Directed Spanner Problem1012.4062v1 · Arnab Bhattacharyya, Konstantin Makarychev2010 · 22 citationsarXiv
Metric Extension Operators, Vertex Sparsifiers and Lipschitz Extendability1006.4607v2 · Konstantin Makarychev, Yury Makarychev2010 · 15 citationsarXiv
How to Play Unique Games on Expanders0903.0367v1 · Konstantin Makarychev, Yury Makarychev2009 · 0 citationsarXiv
Conditionally independent random variablescs/0510029v1 · Konstantin Makarychev, Yury Makarychev2005 · 3 citationsarXiv
Career total: 230 works. 50 are in this corpus.
Profile built from the corpus for this byline.
Author records are still filling in while the Hub is in alpha. If this is your page, you'll be able to claim it soon. Spot a mistake? Tell us.