DescriptionFor 46 years, the best known polynomial-time approximation algorithm for the metric traveling salesman problem was the 1976 Christofides-Serdyukov algorithm, guaranteeing a tour no more than 1.5 times the optimal length. In 2021, Anna Karlin, Nathan Klein, and Shayan Oveis Gharan published the first improvement, achieving a ratio of 3/2 minus a tiny but positive constant (roughly 10^-36), a landmark theoretical result even though the improvement is far too small to matter in any practical implementation, since it establishes that 3/2 is not the best possible approximation ratio for this NP-hard problem.
Formal questionThe Karlin-Klein-Oveis Gharan algorithm achieves a polynomial-time approximation ratio of 3/2 minus a small positive constant (approximately 10^-36) for the metric traveling salesman problem, the first improvement over the Christofides-Serdyukov algorithm's 3/2-approximation ratio since 1976.
Scope auditDoes your result fit this record?
Change a parameter to stress-test whether a proposed result is still inside the published specification. This is an audit aid, not a proof checker.
This record has no editable parameters. Read the formal question and assumptions before challenging it.
Scope matches the published specificationNo parameters changed
