Improving Christofides' Algorithm for the s-t Path TSP

We present a deterministic (1+5/2)-approximation algorithm for the s-t path TSP for an arbitrary metric. Given a symmetric metric cost on n vertices including two prespecified endpoints, the proble...