23 citations · 146 across the 41 of their papers we have counts for
44 papers
Sharper Gaussian Covers in the Bansal--Huang--Lee Coloring Framework
Konstantin Makarychev, Yury Makarychev
Bansal, Huang, and Lee recently gave a polynomial-time algorithm that colors every -colorable graph on vertices with colors. We improve their bound to $O(n^…
Threshold Rounding and Bounded-Degree Boolean MAX 2-CSP
Suprovat Ghoshal, Neng Huang, Euiwoong Lee +2
We describe an -improvement over threshold rounding schemes for a broad class of Boolean MAX 2-CSP instances in which every variable appears in at most cons…
Constraint Satisfaction Problems with Advice
Suprovat Ghoshal, Konstantin Makarychev, Yury Makarychev
We initiate the study of algorithms for constraint satisfaction problems with ML oracle advice. We introduce two models of advice and then design approximation algorithms for Max C…
Higher-Order Cheeger Inequality for Partitioning with Buffers
Konstantin Makarychev, Yury Makarychev, Liren Shan +1
We prove a new generalization of the higher-order Cheeger inequality for partitioning with buffers. Consider a graph . The buffered expansion of a set with…
Approximation Algorithms for Norm Multiway Cut
Charlie Carlson, Jafar Jafarov, Konstantin Makarychev +2
We consider variants of the classic Multiway Cut problem. Multiway Cut asks to partition a graph into parts so as to separate given terminals. Recently, Chandrasekaran…
Single-Pass Pivot Algorithm for Correlation Clustering. Keep it simple!
Sayak Chakrabarty, Konstantin Makarychev
We show that a simple single-pass semi-streaming variant of the Pivot algorithm for Correlation Clustering gives a (3 + ε)-approximation using O(n/ε) words of memory. This is a sli…