= Double-tree approximation for metric TSP
{title2=$\operatorname{ALG}\le2\operatorname{OPT}$}
Double every edge of a <minimum spanning tree> to obtain a connected even-degree multigraph, traverse an <Euler circuit>, and shortcut repeated vertices. The <triangle inequality> prevents any shortcut from increasing cost. Deleting an edge of an optimal tour gives a spanning tree, so the minimum spanning tree has cost at most the optimal tour. The returned tour therefore costs at most twice optimum and is computable in polynomial time. In the relative-error convention this is an error-one approximation.
Back to article page
