From the 1 of 4 linked papers with an AI index.
4 papers
Threshold Rounding and Bounded-Degree Boolean MAX 2-CSP
Suprovat Ghoshal, Neng Huang, Euiwoong Lee +2
The paper presents improved approximation algorithms for Boolean MAX 2-CSP problems on instances where each variable participates in at most d constraints, achieving a ̅Ω(1/d^4) im…
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…