16 - Path TSP by Dynamic Programming

Summary

Traub and Vygen used recursive dynamic programming to obtain a (3/2+ε)-approximation algorithm for Path TSP for any ε>0. This approach was then improved and simplified by Zenklusen, who obtained a 3/2-approximation for Path TSP. After discussing the dynamic programming approach in a simple context, we present Zenklusen’s algorithm.

Then we present a black-box reduction from Path TSP to Symmetric TSP, similar to the one proposed by Traub, Vygen, and Zenklusen. This shows that the former is not much harder to approximate than the latter. This implies the currently best-known approximation guarantees for Path TSP and the special case Graph Path TSP. Our new proof, again based on dynamic programming, actually yields the same result even for a more general problem, which we call Multi-Path TSP.