Reproduce “Improving Christofides' Algorithm for the s-t Path TSP” on OpenResearch
Turn your favorite coding agents into research agents that review literature, develop hypotheses, and run experiments.
Universal app for Apple silicon and Intel. Requires macOS 11 or later.
About this paper
Hyung-Chan An, Robert Kleinberg, David B. Shmoys
Researchers at Cornell University present a deterministic algorithm that achieves a ($1+\sqrt{5}$)/2-approximation for the general metric s-t path Traveling Salesman Problem, breaking the 20-year-old 5/3 approximation barrier. Their work also establishes the first constant upper bound for the integrality gap of the path-variant Held-Karp relaxation and provides improved approximation ratios for related problems.
Key insights
- Sampling a spanning tree from a decomposition of the fractional Held-Karp solution provides a more robust foundation than a simple Minimum Spanning Tree.
- A detailed structural analysis of "narrow cuts" (s-t cuts with small fractional capacity) reveals a layered, non-crossing geometric property essential for tighter bounds.
- The construction of "fractionally disjoint" representative vectors for narrow cuts, leveraging an auxiliary flow network, enables a refined fractional T-join dominator analysis.
Summary by alphaXiv.
Tip: change arxiv.org to autoarxiv.org in any arXiv abstract link to open the paper here.