4 papers
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 a…