An LP-based 3/2-approximation algorithm for the graphic s-t path TSP

Zhihan Gao

We design a new LP-based algorithm for the graphic $s$-$t$ path Traveling Salesman Problem (TSP), which achieves the best approximation factor of 1.5. The algorithm is based on the…