# A (Slightly) Improved Approximation Algorithm for Metric TSP

arXiv: https://arxiv.org/abs/2007.01409 · HTML: https://mlsanity.com/paper/2007.01409/

## Key facts

- Cited by 13 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 2 Jul 2020.

## Built on by (most cited first, 13 of 13)

- [Neural Algorithmic Reasoning for Combinatorial Optimisation](https://mlsanity.com/paper/2306.06064/) (2023)
- [FrontierCO: Real-World and Large-Scale Evaluation of Machine Learning Solvers for Combinatorial Optimization](https://mlsanity.com/paper/2505.16952/) (2025)
- [Reinforced Generation of Combinatorial Structures: Hardness of Approximation](https://mlsanity.com/paper/2509.18057/) (2025)
- [Optimal Sublinear Sampling of Spanning Trees and Determinantal Point Processes via Average-Case Entropic Independence](https://mlsanity.com/paper/2204.02570/) (2022)
- [Set-to-Sequence Methods in Machine Learning: a Review](https://mlsanity.com/paper/2103.09656/) (2021)
- [Learning-Based Algorithms for Graph Searching Problems](https://mlsanity.com/paper/2402.17736/) (2024)
- [On Cyclic Solutions to the Min-Max Latency Multi-Robot Patrolling Problem](https://mlsanity.com/paper/2203.07280/) (2022)
- [Navigating Intelligence: A Survey of Google OR-Tools and Machine Learning for Global Path Planning in Autonomous Vehicles](https://mlsanity.com/paper/2503.03338/) (2025)
- [Graph Neural Networks are Heuristics](https://mlsanity.com/paper/2601.13465/) (2026)
- [TSP with Predictions: Heatmap to Tour with Provable Guarantees](https://mlsanity.com/paper/2607.03791/) (2026)
- [Recycling computational processes of dynamic programming for combinatorial optimization problems: a reservoir computing approach](https://mlsanity.com/paper/2607.23009/) (2026)
- [On the Triangle Inequality for the Jaccard Distance in Arbitrary Lattices](https://mlsanity.com/paper/2608.18194/) (2026)
- [Self-Supervised Combinatorial Optimization with Constraints via Frank-Wolfe](https://mlsanity.com/paper/2609.25728/) (2026)

## Abstract (arXiv)

For some ε > 10-36 we give a randomized 3/2-ε approximation algorithm for metric TSP.