From the 1 of 5 linked papers with an AI index.
5 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…
Max Cut with Small-Dimensional SDP Solutions
Hsien-Chih Chang, Suprovat Ghoshal, Euiwoong Lee
We study the Max-Cut semidefinite programming (SDP) relaxation in the regime where a near-optimal solution admits a low-dimensional realization. While the Goemans--Williamson hyper…
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 SDP-Based Algorithm for Coloring 3-Colorable Graphs
Nikhil Bansal, Neng Huang, Euiwoong Lee
We present a polynomial-time algorithm that colors any 3-colorable -vertex graph using colors, improving upon the previous best bound of $\widetilde{O}(n^{0.197…
Approximating Maximum Cut on Interval Graphs and Split Graphs beyond Goemans-Williamson
Jungho Ahn, Ian DeHaan, Eun Jung Kim +1
We present a polynomial-time -approximation algorithm for the Maximum Cut problem on interval graphs and split graphs, where is the…