

























We present a polynomial-time $(α_{GW} + \varepsilon)$-approximation algorithm for the Maximum Cut problem on interval graphs and split graphs, where $α_{GW} \approx 0.878$ is the approximation guarantee of the Goemans-Williamson algorithm and $\varepsilon > 10^{-34}$ is a fixed constant. To attain this, we give an improved analysis of a slight modification of the Goemans-Williamson algorithm for graphs in which triangles can be packed into a constant fraction of their edges. We then pair this analysis with structural results showing that both interval graphs and split graphs either have such a triangle packing or have maximum cut close to their number of edges. We also show that, subject to the Small Set Expansion Hypothesis, there exists a constant $c > 0$ such that there is no polyomial-time $(1 - c)$-approximation for Maximum Cut on split graphs.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。