×

zbMATH — the first resource for mathematics

Makarychev, Konstantin S.

Compute Distance To:
Author ID: makarychev.konstantin-s Recent zbMATH articles by "Makarychev, Konstantin S."
Published as: Makarychev, K.; Makarychev, Konstantin; Makarychev, Konstantin S.
Documents Indexed: 53 Publications since 2002, including 1 Book

Publications by Year

Citations contained in zbMATH

37 Publications have been cited 221 times in 196 Documents Cited by Year
\(O(\sqrt{\log n})\) approximation algorithms for Min UnCut, Min 2CNF deletion, and directed cut problems. Zbl 1192.68864
Agarwal, Amit; Charikar, Moses; Makarychev, Konstantin; Makarychev, Yury
32
2005
Integrality gaps for Sherali-Adams relaxations. Zbl 1304.90143
Charikar, Moses; Makarychev, Konstantin; Makarychev, Yury
23
2009
Near-optimal algorithms for unique games. Zbl 1301.68267
Charikar, Moses; Makarychev, Konstantin; Makarychev, Yury
16
2006
Quadratic forms on graphs. Zbl 1082.05051
Alon, Noga; Makarychev, Konstantin; Makarychev, Yury; Naor, Assaf
16
2006
Metric extension operators, vertex sparsifiers and Lipschitz extendability. Zbl 1341.05104
Makarychev, Konstantin; Makarychev, Yury
15
2016
The Grothendieck constant is strictly smaller than Krivine’s bound. Zbl 1292.90243
Braverman, Mark; Makarychev, Konstantin; Makarychev, Yury; Naor, Assaf
13
2011
A new class of non-Shannon-type inequalities for entropies. Zbl 1094.94017
Makarychev, Konstantin; Makarychev, Yury; Romashchenko, Andrei; Vereshchagin, Nikolai
11
2002
The Grothendieck constant is strictly smaller than Krivine’s bound. Zbl 1320.15016
Braverman, Mark; Makarychev, Konstantin; Makarychev, Yury; Naor, Assaf
7
2013
On hardness of pricing items for single-minded bidders. Zbl 1255.68075
Khandekar, Rohit; Kimbrel, Tracy; Makarychev, Konstantin; Sviridenko, Maxim
7
2009
Directed metrics and directed graph partitioning problems. Zbl 1192.90219
Charikar, Moses; Makarychev, Konstantin; Makarychev Yury
7
2006
Approximation algorithms for spanner problems and directed Steiner forest. Zbl 1267.68317
Berman, Piotr; Bhattacharyya, Arnab; Makarychev, Konstantin; Raskhodnikova, Sofya; Yaroslavtsev, Grigory
6
2013
Local global tradeoffs in metric embeddings. Zbl 1206.68138
Charikar, Moses; Makarychev, Konstantin; Makarychev, Yury
6
2010
Quadratic forms on graphs (extended abstract). Zbl 1192.05168
Alon, Noga; Makarychev, Konstantin; Makarychev, Yury; Naor, Assaf
6
2005
Improved approximation for the directed spanner problem. Zbl 1332.68283
Berman, Piotr; Bhattacharyya, Arnab; Makarychev, Konstantin; Raskhodnikova, Sofya; Yaroslavtsev, Grigory
5
2011
Near-optimal algorithms for maximum constraint satisfaction problems. Zbl 1298.68111
Charikar, Moses; Makarychev, Konstantin; Makarychev, Yury
5
2009
Constant factor approximation for balanced cut in the PIE model. Zbl 1315.05114
Makarychev, Konstantin; Makarychev, Yury; Vijayaraghavan, Aravindan
4
2014
Min-max graph partitioning and small set expansion. Zbl 1292.05126
Bansal, Nikhil; Feige, Uriel; Krauthgamer, Robert; Makarychev, Konstantin; Nagarajan, Viswanath; Naor, Joseph; Schwartz, Roy
4
2011
Online make-to-order joint replenishment model: Primal dual competitive algorithms. Zbl 1192.90005
Buchbinder, N.; Kimbrel, T.; Levi, R.; Makarychev, K.; Sviridenko, M.
4
2008
A bi-criteria approximation algorithm for \(k\)-means. Zbl 1398.68680
Makarychev, Konstantin; Makarychev, Yury; Sviridenko, Maxim; Ward, Justin
3
2016
Near optimal LP rounding algorithm for correlation clustering on complete and complete \(k\)-partite graphs. Zbl 1321.68495
Chawla, Shuchi; Makarychev, Konstantin; Schramm, Tselil; Yaroslavtsev, Grigory
3
2015
Approximation algorithm for sparsest \(k\)-partitioning. Zbl 1422.68306
Louis, Anand; Makarychev, Konstantin
3
2014
Min-max graph partitioning and small set expansion. Zbl 1360.68639
Bansal, Nikhil; Feige, Uriel; Krauthgamer, Robert; Makarychev, Konstantin; Nagarajan, Viswanath; Naor, Joseph (Seffi); Schwartz, Roy
3
2014
Performance of Johnson-Lindenstrauss transform for \(k\)-means and \(k\)-medians clustering. Zbl 1433.68366
Makarychev, Konstantin; Makarychev, Yury; Razenshteyn, Ilya
2
2019
Algorithms for stable and perturbation-resilient problems. Zbl 1370.68115
Angelidakis, Haris; Makarychev, Konstantin; Makarychev, Yury
2
2017
Online make-to-order joint replenishment model: primal-dual competitive algorithms. Zbl 1291.90010
Buchbinder, Niv; Kimbrel, Tracy; Levi, Retsef; Makarychev, Konstantin; Sviridenko, Maxim
2
2013
How to play unique games on expanders. Zbl 1314.68401
Makarychev, Konstantin; Makarychev, Yury
2
2011
Maximum quadratic assignment problem: reduction from maximum label cover and LP-based approximation algorithm. Zbl 1288.68273
Makarychev, Konstantin; Manokaran, Rajsekar; Sviridenko, Maxim
2
2010
A divide and conquer algorithm for \(d\)-dimensional arrangement. Zbl 1302.68315
Charikar, Moses; Makarychev, Konstantin; Makarychev, Yury
2
2007
Near-optimal algorithms for maximum constraint satisfaction problems. Zbl 1302.68134
Charikar, Moses; Makarychev, Konstantin; Makarychev, Yury
2
2007
Solving optimization problems with diseconomies of scale via decoupling. Zbl 1426.90261
Makarychev, Konstantin; Sviridenko, Maxim
1
2018
Robust algorithms with polynomial loss for near-unanimity CSPs. Zbl 1410.68162
Dalmau, Víctor; Kozik, Marcin; Krokhin, Andrei; Makarychev, Konstantin; Makarychev, Yury; Opršal, Jakub
1
2017
Bilu-Linial stable instances of max cut and minimum multiway cut. Zbl 1422.68127
Makarychev, Konstantin; Makarychev, Yury; Vijayaraghavan, Aravindan
1
2014
Approximation algorithm for non-Boolean Max-\(k\)-CSP. Zbl 1319.68254
Makarychev, Konstantin; Makarychev, Yury
1
2014
Sorting noisy data with partial information. Zbl 1362.68293
Makarychev, Konstantin; Makarychev, Yury; Vijayaraghavan, Aravindan
1
2013
Approximation algorithms for semi-random partitioning problems. Zbl 1286.68504
Makarychev, Konstantin; Makarychev, Yury; Vijayaraghavan, Aravindan
1
2012
Approximation algorithm for non-Boolean MAX \(k\)-CSP. Zbl 1319.68253
Makarychev, Konstantin; Makarychev, Yury
1
2012
On parsimonious explanations for 2-D tree- and linearly-ordered data. Zbl 1230.68067
Karloff, Howard; Korn, Flip; Makarychev, Konstantin; Rabani, Yuval
1
2011
Performance of Johnson-Lindenstrauss transform for \(k\)-means and \(k\)-medians clustering. Zbl 1433.68366
Makarychev, Konstantin; Makarychev, Yury; Razenshteyn, Ilya
2
2019
Solving optimization problems with diseconomies of scale via decoupling. Zbl 1426.90261
Makarychev, Konstantin; Sviridenko, Maxim
1
2018
Algorithms for stable and perturbation-resilient problems. Zbl 1370.68115
Angelidakis, Haris; Makarychev, Konstantin; Makarychev, Yury
2
2017
Robust algorithms with polynomial loss for near-unanimity CSPs. Zbl 1410.68162
Dalmau, Víctor; Kozik, Marcin; Krokhin, Andrei; Makarychev, Konstantin; Makarychev, Yury; Opršal, Jakub
1
2017
Metric extension operators, vertex sparsifiers and Lipschitz extendability. Zbl 1341.05104
Makarychev, Konstantin; Makarychev, Yury
15
2016
A bi-criteria approximation algorithm for \(k\)-means. Zbl 1398.68680
Makarychev, Konstantin; Makarychev, Yury; Sviridenko, Maxim; Ward, Justin
3
2016
Near optimal LP rounding algorithm for correlation clustering on complete and complete \(k\)-partite graphs. Zbl 1321.68495
Chawla, Shuchi; Makarychev, Konstantin; Schramm, Tselil; Yaroslavtsev, Grigory
3
2015
Constant factor approximation for balanced cut in the PIE model. Zbl 1315.05114
Makarychev, Konstantin; Makarychev, Yury; Vijayaraghavan, Aravindan
4
2014
Approximation algorithm for sparsest \(k\)-partitioning. Zbl 1422.68306
Louis, Anand; Makarychev, Konstantin
3
2014
Min-max graph partitioning and small set expansion. Zbl 1360.68639
Bansal, Nikhil; Feige, Uriel; Krauthgamer, Robert; Makarychev, Konstantin; Nagarajan, Viswanath; Naor, Joseph (Seffi); Schwartz, Roy
3
2014
Bilu-Linial stable instances of max cut and minimum multiway cut. Zbl 1422.68127
Makarychev, Konstantin; Makarychev, Yury; Vijayaraghavan, Aravindan
1
2014
Approximation algorithm for non-Boolean Max-\(k\)-CSP. Zbl 1319.68254
Makarychev, Konstantin; Makarychev, Yury
1
2014
The Grothendieck constant is strictly smaller than Krivine’s bound. Zbl 1320.15016
Braverman, Mark; Makarychev, Konstantin; Makarychev, Yury; Naor, Assaf
7
2013
Approximation algorithms for spanner problems and directed Steiner forest. Zbl 1267.68317
Berman, Piotr; Bhattacharyya, Arnab; Makarychev, Konstantin; Raskhodnikova, Sofya; Yaroslavtsev, Grigory
6
2013
Online make-to-order joint replenishment model: primal-dual competitive algorithms. Zbl 1291.90010
Buchbinder, Niv; Kimbrel, Tracy; Levi, Retsef; Makarychev, Konstantin; Sviridenko, Maxim
2
2013
Sorting noisy data with partial information. Zbl 1362.68293
Makarychev, Konstantin; Makarychev, Yury; Vijayaraghavan, Aravindan
1
2013
Approximation algorithms for semi-random partitioning problems. Zbl 1286.68504
Makarychev, Konstantin; Makarychev, Yury; Vijayaraghavan, Aravindan
1
2012
Approximation algorithm for non-Boolean MAX \(k\)-CSP. Zbl 1319.68253
Makarychev, Konstantin; Makarychev, Yury
1
2012
The Grothendieck constant is strictly smaller than Krivine’s bound. Zbl 1292.90243
Braverman, Mark; Makarychev, Konstantin; Makarychev, Yury; Naor, Assaf
13
2011
Improved approximation for the directed spanner problem. Zbl 1332.68283
Berman, Piotr; Bhattacharyya, Arnab; Makarychev, Konstantin; Raskhodnikova, Sofya; Yaroslavtsev, Grigory
5
2011
Min-max graph partitioning and small set expansion. Zbl 1292.05126
Bansal, Nikhil; Feige, Uriel; Krauthgamer, Robert; Makarychev, Konstantin; Nagarajan, Viswanath; Naor, Joseph; Schwartz, Roy
4
2011
How to play unique games on expanders. Zbl 1314.68401
Makarychev, Konstantin; Makarychev, Yury
2
2011
On parsimonious explanations for 2-D tree- and linearly-ordered data. Zbl 1230.68067
Karloff, Howard; Korn, Flip; Makarychev, Konstantin; Rabani, Yuval
1
2011
Local global tradeoffs in metric embeddings. Zbl 1206.68138
Charikar, Moses; Makarychev, Konstantin; Makarychev, Yury
6
2010
Maximum quadratic assignment problem: reduction from maximum label cover and LP-based approximation algorithm. Zbl 1288.68273
Makarychev, Konstantin; Manokaran, Rajsekar; Sviridenko, Maxim
2
2010
Integrality gaps for Sherali-Adams relaxations. Zbl 1304.90143
Charikar, Moses; Makarychev, Konstantin; Makarychev, Yury
23
2009
On hardness of pricing items for single-minded bidders. Zbl 1255.68075
Khandekar, Rohit; Kimbrel, Tracy; Makarychev, Konstantin; Sviridenko, Maxim
7
2009
Near-optimal algorithms for maximum constraint satisfaction problems. Zbl 1298.68111
Charikar, Moses; Makarychev, Konstantin; Makarychev, Yury
5
2009
Online make-to-order joint replenishment model: Primal dual competitive algorithms. Zbl 1192.90005
Buchbinder, N.; Kimbrel, T.; Levi, R.; Makarychev, K.; Sviridenko, M.
4
2008
A divide and conquer algorithm for \(d\)-dimensional arrangement. Zbl 1302.68315
Charikar, Moses; Makarychev, Konstantin; Makarychev, Yury
2
2007
Near-optimal algorithms for maximum constraint satisfaction problems. Zbl 1302.68134
Charikar, Moses; Makarychev, Konstantin; Makarychev, Yury
2
2007
Near-optimal algorithms for unique games. Zbl 1301.68267
Charikar, Moses; Makarychev, Konstantin; Makarychev, Yury
16
2006
Quadratic forms on graphs. Zbl 1082.05051
Alon, Noga; Makarychev, Konstantin; Makarychev, Yury; Naor, Assaf
16
2006
Directed metrics and directed graph partitioning problems. Zbl 1192.90219
Charikar, Moses; Makarychev, Konstantin; Makarychev Yury
7
2006
\(O(\sqrt{\log n})\) approximation algorithms for Min UnCut, Min 2CNF deletion, and directed cut problems. Zbl 1192.68864
Agarwal, Amit; Charikar, Moses; Makarychev, Konstantin; Makarychev, Yury
32
2005
Quadratic forms on graphs (extended abstract). Zbl 1192.05168
Alon, Noga; Makarychev, Konstantin; Makarychev, Yury; Naor, Assaf
6
2005
A new class of non-Shannon-type inequalities for entropies. Zbl 1094.94017
Makarychev, Konstantin; Makarychev, Yury; Romashchenko, Andrei; Vereshchagin, Nikolai
11
2002
all top 5

Cited by 395 Authors

10 Naor, Assaf
7 Pokutta, Sebastian
6 Khot, Subhash Ajit
5 Pilipczuk, Marcin
4 Braun, Gábor
4 Fiorini, Samuel
4 Hajiaghayi, Mohammad Taghi
4 Raghavendra, Prasad
4 Saket, Rishi
4 Xu, Dachuan
3 Briët, Jop
3 Elkin, Michael
3 Goranci, Gramoz
3 Guruswami, Venkatesan
3 Kenkre, Sreyash
3 Kratsch, Stefan
3 Krokhin, Andrei A.
3 Makarychev, Konstantin S.
3 Niedermeier, Rolf
3 Palazuelos, Carlos
3 Pellegrino, Daniel Marinho
3 Regev, Oded
3 Sanità, Laura
3 Saurabh, Saket
3 So, Anthony Man-Cho
3 Wu, Chenchen
3 Wu, Yi
3 Zhang, Peng
2 Ahmadian, Sara
2 Alon, Noga M.
2 Balakrishnan, Anantaram
2 Barenboim, Leonid
2 Bienkowski, Marcin
2 Byrka, Jarosław
2 Chan, T.-H. Hubert
2 Charikar, Moses S.
2 Chitnis, Rajesh Hemant
2 Chrobak, Marek
2 Cordón-Franco, Andrés
2 Dalmau, Víctor
2 Elmachtoub, Adam N.
2 Fernández Duque, David
2 Filtser, Arnold
2 Friedland, Shmuel
2 Gavoille, Cyril
2 Georgiou, Konstantinos
2 Hosseinzadeh, Hamideh
2 Hüffner, Falk
2 Jansen, Bart M. P.
2 Karpov, Nikolai
2 Kozik, Marcin
2 Krauthgamer, Robert
2 Laurent, Monique
2 Levi, Retsef
2 Li, Gang
2 Lim, Lek-Heng
2 Makarychev, Yury S.
2 Mishra, Sounaka
2 Neiman, Ofer
2 Pandit, Vinayaka
2 Peng, Pan
2 Pilipczuk, Michał
2 Purohit, Manish
2 Racke, Harald
2 Rauch Henzinger, Monika
2 Roy, Aurko
2 Seoane-Sepúlveda, Juan Benigno
2 Sidiropoulos, Anastasios
2 Singer, Amit
2 Soler-Toscano, Fernando
2 Steurer, David
2 Suchý, Ondřej
2 Sviridenko, Maxim I.
2 Tunçel, Levent
2 van Ditmarsch, Hans Pieter
2 Varvitsiotis, Antonios E.
2 Vidick, Thomas
2 Zhang, Dongmei
2 Zhang, Jinjie
2 Zhang, Zhenning
2 Zhou, Yuan
2 Zych-Pawlewicz, Anna
1 Abraham, Ittai
1 Abu-Ata, Muad
1 Alekhnovich, Michael
1 Ambainis, Andris
1 Arora, Sanjeev
1 Arunachalam, Srinivasan
1 Ashkboos, Saleh
1 Aspnes, James
1 Au, Yu-Hin
1 Avidor, Adi
1 Avis, David M.
1 Bachoc, Christine
1 Bandeira, Afonso S.
1 Bansal, Nikhil
1 Barak, Boaz
1 Barroso, Manuel A.
1 Bartal, Yair
1 Barto, Libor
...and 295 more Authors
all top 5

Cited in 68 Serials

19 Theoretical Computer Science
16 SIAM Journal on Computing
13 Mathematical Programming. Series A. Series B
10 Journal of Computer and System Sciences
9 Algorithmica
7 Information Processing Letters
6 Discrete Optimization
5 SIAM Journal on Discrete Mathematics
5 Journal of Combinatorial Optimization
4 Mathematics of Operations Research
4 Operations Research
3 Communications in Mathematical Physics
3 Operations Research Letters
3 Computational Complexity
2 Israel Journal of Mathematics
2 Probability Theory and Related Fields
2 European Journal of Operational Research
2 Linear Algebra and its Applications
2 Bulletin of the American Mathematical Society. New Series
2 SIAM Journal on Optimization
2 Journal of the ACM
1 Communications on Pure and Applied Mathematics
1 Discrete Applied Mathematics
1 Discrete Mathematics
1 Journal of Mathematical Physics
1 Linear and Multilinear Algebra
1 Moscow University Mathematics Bulletin
1 Problems of Information Transmission
1 Annales de l’Institut Fourier
1 Journal of Combinatorial Theory. Series B
1 Mathematika
1 Memoirs of the American Mathematical Society
1 Networks
1 Numerische Mathematik
1 Proceedings of the American Mathematical Society
1 Transactions of the American Mathematical Society
1 European Journal of Combinatorics
1 Journal of Time Series Analysis
1 Journal of Computer Science and Technology
1 Discrete & Computational Geometry
1 Information and Computation
1 Computers & Operations Research
1 Random Structures & Algorithms
1 Journal of Global Optimization
1 Designs, Codes and Cryptography
1 L’Enseignement Mathématique. 2e Série
1 Proceedings of the National Academy of Sciences of the United States of America
1 Computational Optimization and Applications
1 SIAM Journal on Scientific Computing
1 Applied and Computational Harmonic Analysis
1 Sbornik: Mathematics
1 Theory of Computing Systems
1 Journal of Scheduling
1 Annals of Combinatorics
1 New Journal of Physics
1 Annals of Mathematics. Second Series
1 Communications in Contemporary Mathematics
1 Entropy
1 Journal of Machine Learning Research (JMLR)
1 Bulletin of the Brazilian Mathematical Society. New Series
1 Quantum Information Processing
1 Journal of Statistical Mechanics: Theory and Experiment
1 Foundations of Physics
1 Chebyshevskiĭ Sbornik
1 Japanese Journal of Mathematics. 3rd Series
1 Analysis and Geometry in Metric Spaces
1 ACM Transactions on Computation Theory
1 Proceedings of the Royal Society of London. A. Mathematical, Physical and Engineering Sciences

Citations by Year