6 papers
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…
Improved Approximation Algorithms for Multiway Cut by Large Mixtures of New and Old Rounding Schemes
Joshua Brakensiek, Neng Huang, Aaron Potechin +1
The input to the Multiway Cut problem is a weighted undirected graph, with nonnegative edge weights, and designated terminals. The goal is to partition the vertices of the grap…
MAX BISECTION might be harder to approximate than MAX CUT
Joshua Brakensiek, Neng Huang, Aaron Potechin +1
The MAX BISECTION problem seeks a maximum-size cut that evenly divides the vertices of a given undirected graph. An open problem raised by Austrin, Benabbas, and Georgiou is whethe…
Hardness of sampling for the anti-ferromagnetic Ising model on random graphs
Neng Huang, Will Perkins, Aaron Potechin
We prove a hardness of sampling result for the anti-ferromagnetic Ising model on random graphs of average degree for large constant , proving that when the normalized invers…
Tight approximability of MAX 2-SAT and relatives, under UGC
Joshua Brakensiek, Neng Huang, Uri Zwick
Austrin showed that the approximation ratio obtained by the MAX 2-SAT approximation algorithm of Lewin, Livnat and Zwick (LLZ) is optimal modulo the Unique Ga…