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