Some Complexity Results 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. The Traveling Salesman Problem is also shown to be NP-Complete even if its instances are restricted to be realizable by a set of points on the Euclidean plane.
BibTeX
@inproceedings{papadimitriou1976some,
author = {Christos H. Papadimitriou and Kenneth Steiglitz},
title = {{Some Complexity Results for the Traveling Salesman Problem}},
booktitle = {STOC},
year = {1976},
doi = {10.1145/800113.803625},
}Loading related content...