On the Metric $s$--$t$ Path Traveling Salesman Problem
On the Metric $s$--$t$ Path Traveling Salesman Problem
We study the metric $s$--$t$ path traveling salesman problem (TSP). An, Kleinberg, and Shmoys [Proceedings of the 44th ACM Symposium on Theory of Computing, 2012, pp. 875--886] improved on the long-standing $\frac{5}{3}$-approximation factor and presented an algorithm that achieves an approximation factor of $\frac{1+\sqrt{5}}{2}\approx1.61803$. Later, Sebö [Proceedings of the 16th …