(E) Quanta Magazine has a new interesting article “Computer Scientists Break Traveling Salesperson Record“. The new record was broken by PhD student Nathan Klein and his advisers from the University of Washington, and described in two papers:

• “An Improved Approximation Algorithm for TSP in the Half Integral Case“

• “A (Slightly) Improved Approximation Algorithm for Metric TSP“

Video talk

Note 1: A new easy-to-read article from Nathan:”Planning the best route with multiple destinations is hard even for supercomputers – a new approach breaks a barrier that’s stood for nearly half a century“

Note 2: Summary of complexity theory:

• P = solved in polynomial time
• NP  = non-deterministic polynomial time
• NP = verified in polynomial time or solved in polynomial time on non-deterministic Turing machine
• P problems are always NP
• NP problems are difficult to solve but easy to verified
• NP-hard = algorithm for solving it can be translated to solve any other NP problem – note that NP-hard are not necessarily NP problems
• NP-complete = both NP and NP-hard
• Traveling salesperson is NP-complete
• P non-equal to NP = currently unknown = every problem that can be verified by a computer can be solved by a computer

Note 3: The picture above is from one of Nathan’s talk.

Copyright © 2005-2020 by Serge-Paul Carrasco. All rights reserved.
Contact Us: asvinsider at gmail dot com