On the Complexity of Local Search for the Traveling Salesman Problem
Lists
Only you see this
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...