On the Complexity of Local Search for the Traveling Salesman Problem

Christos H. Papadimitriou, Kenneth SteiglitzSIAM Journal on Computing 1977 · OpenReview

Abstract

It is shown that, unless $P = NP$, local search algorithms for the traveling salesman problem having polynomial time complexity per iteration will generate solutions arbitrarily far from the optimal. Keywords traveling salesman problem local search complexity NP-complete
BibTeX
@article{papadimitriou1977complexity,
  author = {Christos H. Papadimitriou and Kenneth Steiglitz},
  title = {{On the Complexity of Local Search for the Traveling Salesman Problem}},
  journal = {SIAM Journal on Computing},
  year = {1977},
  url = {https://openreview.net/forum?id=wMwGqgOcoVH},
}

Loading related content...

Figure