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. MSC codes traveling salesman problem local search complexity NP-complete
No takes yet. Share an insight, caveat, or question.
Papadimitriou et al. (1977) studied this question.
Synapse has enriched 5 closely related papers on similar clinical questions. Consider them for comparative context: