A Polynomial Time Algorithm for The Traveling Salesman Problem

Abstract

The ATSP polytope can be expressed by asymmetric polynomial size linear program.

8 pages. Simplified

Cited by in corpus (4)

• Why Linear Programming cannot solve large instances of NP-complete problems in polynomial time
• A Polynomial Time Algorithm for 3-SAT
• Report on article The Travelling Salesman Problem: A Linear Programming Formulation
• Reducing SAT to 2-SAT