


























We show that for some $ε> 10^{-36}$ and any metric TSP instance, the max entropy algorithm returns a solution of expected cost at most $\frac{3}{2}-ε$ times the cost of the optimal solution to the subtour elimination LP. This implies that the integrality gap of the subtour LP is at most $\frac{3}{2}-ε$. This analysis also shows that there is a randomized $\frac{3}{2}-ε$ approximation for the 2-edge-connected multi-subgraph problem, improving upon Christofides' algorithm.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。