Papers of the day   All papers

A (Slightly) Improved Approximation Algorithm for Metric TSP

Comments

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 🤣 https://arxiv.org/pdf/2007.01409.pdf https://t.co/PDJLLa6v94

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." https://arxiv.org/abs/2007.01409

5 replies, 107 likes


JohannesBorgen: This is fantastic. After 46 years, researchers have finally improved Christofides' algorithm on the traveling salesman problem. https://arxiv.org/abs/2007.01409 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 ⏯️https://arxiv.org/abs/2007.01409 ⏯️https://mathworld.wolfram.com/TravelingSalesmanProblem.html https://www.quantamagazine.org/computer-scientists-break-traveling-salesperson-record-20201008/

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. https://arxiv.org/pdf/2007.01409.pdf https://t.co/xjC2LDrSis

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: https://arxiv.org/abs/2007.01409. https://t.co/5ZPn8k8y8y

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: https://arxiv.org/abs/2007.01409 https://www.wired.com/story/computer-scientists-break-the-traveling-salesperson-record

0 replies, 1 likes


Content

Found on Jul 08 2020 at https://arxiv.org/pdf/2007.01409.pdf

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