论文标题
在有界度图上近似最大切割：FKL算法的更严格的分析
Approximating Max-Cut on Bounded Degree Graphs: Tighter Analysis of the FKL Algorithm
论文作者
论文摘要
在本说明中，我们描述了$α_{gw} + \tildeΩ（1/d^2）$ - 在$ \ leq d $的加权图上最大切割的factor actial近似算法。在这里，$α_{gw} \大约0.878 $是用于最大切割的goemans-williamson圆形的最差案例近似值。这改善了Feige，Karpinski和Langberg and Florre的先前未加权图的结果。我们的保证是通过对解决方案的更严格的分析，通过将自然的局部改进程序应用于以三角形不平等增强的基本SDP的goemans-williamson圆形。
In this note, we describe a $α_{GW} + \tildeΩ(1/d^2)$-factor approximation algorithm for Max-Cut on weighted graphs of degree $\leq d$. Here, $α_{GW}\approx 0.878$ is the worst-case approximation ratio of the Goemans-Williamson rounding for Max-Cut. This improves on previous results for unweighted graphs by Feige, Karpinski, and Langberg and Florén. Our guarantee is obtained by a tighter analysis of the solution obtained by applying a natural local improvement procedure to the Goemans-Williamson rounding of the basic SDP strengthened with triangle inequalities.
