13 citations · 14 across the 8 of their papers we have counts for
14 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^…
Socially Fair Clustering: Parameterized Approximation and Local Search
Aditya Anand, Yury Makarychev, Liren Shan
We study the Socially Fair Clustering problem introduced by Abbasi, Bhaskara, and Venkatasubramanian (2021) and Ghadiri, Samadi, and Vempala (2021), along with its extension, the $…
Sharp Analysis of Gaussian Rounding for Boolean Max k-CSP
Yury Makarychev
In this note, we show that the approximation algorithm for Boolean Max -CSP presented in [Makarychev and Makarychev 2014] yields a approximation, as conjecture…
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…
On the Approximability of Max-Cut on 3-Colorable Graphs and Graphs with Large Independent Sets
Suprovat Ghoshal, Neng Huang, Euiwoong Lee +2
Max-Cut is a classical graph-partitioning problem where given a graph , the objective is to find a cut which maximizes the number of edges crossing the cut. In…
Hardness of Approximation for Shortest Path with Vector Costs
Charlie Carlson, Yury Makarychev, Ron Mosenzon
We obtain hardness of approximation results for the -Shortest Path problem, a variant of the classic Shortest Path problem with vector costs. For every integer $p \in [2,\i…