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 $({\alpha }_{GW}+\epsilon )$-approximation algorithm for the Maximum Cut problem on interval graphs and split graphs, where ${\alpha }_{GW}\approx 0.878$ is the a…