solidot新版网站常见问题,请点击这里查看。
消息
本文已被查看830次
Approaching $\frac{3}{2}$ for the $s$-$t$-path TSP. (arXiv:1707.03992v1 [cs.DM])
来源于:arXiv
We show that there is a polynomial-time algorithm with approximation
guarantee $\frac{3}{2}+\epsilon$ for the $s$-$t$-path TSP, for any fixed
$\epsilon>0$.
It is well known that Wolsey's analysis of Christofides' algorithm also works
for the $s$-$t$-path TSP with its natural LP relaxation except for the narrow
cuts (in which the LP solution has value less than two). A fixed optimum tour
has either a single edge in a narrow cut (then call the edge and the cut
lonely) or at least three (then call the cut busy). Our algorithm "guesses" (by
dynamic programming) lonely cuts and edges. Then we partition the instance into
smaller instances and strengthen the LP, requiring value at least three for
busy cuts. By setting up a $k$-stage recursive dynamic program, we can compute
a spanning tree $(V,S)$ and an LP solution $y$ such that
$(\frac{1}{2}+O(2^{-k}))y$ is in the $T$-join polyhedron, where $T$ is the set
of vertices whose degree in $S$ has the wrong parity. 查看全文>>