The Euclidean Traveling Salesman Problem is NP-Complete

By Christos H. Papadimitriou. 1977

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

1. Yoshua Bengio
2. Quoc V. Le
3. Hieu Pham
4. Irwan Bello
5. Mohammad Norouzi
6. Mohit Bansal
7. Sergey Levine
8. Ruslan Salakhutdinov

Citations in the corpus

• Neural Combinatorial Optimization with Reinforcement Learning (2016, methodology): “We compare learning the network parameters on a set of training graphs against learning them on individual test graphs.”
• On the Complexity of Nash Equilibria and Other Fixed Points (Extended Abstract) (2010, background): “, [18, 34, 40]) whether it is solvable even in NP (or better yet, in P).”
• An Efficient Graph Convolutional Network Technique for the Travelling Salesman Problem (2019, background): “Finding the optimal TSP solution is NP-hard, even in the 2D Euclidean case where the nodes are 2D points and edge weights are Euclidean distances between pairs of points [Papadimitriou, 1977].”
• Message ferrying: proactive routing in highly-partitioned wireless ad hoc networks (2003, background): “Since the Euclidean Traveling Salesman Problem is NP-complete [10], we prove that the MFR-delay problem is NP-hard.”