Papers of the day   All papers

A (Slightly) Improved Approximation Algorithm for Metric TSP


Reza Zadeh: The Traveling Salesman Problem approximation ratio hasn't improved from 3/2 since 1976, via MST + Minimum-Weight Perfect Matching + Eulerian Shortcuts. The 3/2 barrier has been broken after 44 years! The abstract is one sentence, the paper is 85 pages 🤣

4 replies, 560 likes

Bill Cook: Anna Karlin, Nathan Klein, and @oveisgharan have improved Christofides algorithm! You gotta love the 1-line abstract: "For some ϵ>10^−36 we give a 3/2−ϵ approximation algorithm for metric TSP."

5 replies, 107 likes

JohannesBorgen: This is fantastic. After 46 years, researchers have finally improved Christofides' algorithm on the traveling salesman problem. Ok, the improvement is (not kidding here) 0,00000000000000000000000000000000010% but it's still great 😂

2 replies, 23 likes

Chris Anderson: The abstract is one sentence, the paper is 85 pages

2 replies, 19 likes

Manuela Casasoli: "After 44 years, there’s finally a better way to find approximate solutions to the notoriously difficult traveling salesperson problem." #Mathematics #maths #Math #mtbos @QuantaMagazine ⏯️ ⏯️

0 replies, 11 likes

Lukasz Olejnik: Finally, after half a century there's a better (approximate) algorithm for the traveling salesperson problem. Crucial in many domains, from DNA sequencing to travel plans/logistics. It's not even magic.

0 replies, 4 likes

Alex Teytelboym: If you're a travelling salesman, you're about to find out how to save yourself a lot of time. This paper seems like a pretty big deal:

0 replies, 3 likes

EA Aguilar: The traveling salesperson will be able to spend more time with their family now :') #beautifulmathematics

0 replies, 2 likes

Philip Thrift: ref:

0 replies, 1 likes


Found on Jul 08 2020 at

PDF content of a computer science paper: A (Slightly) Improved Approximation Algorithm for Metric TSP