Abstract
We prove that the local search optimization problem TSP2Opt, though not known to be PLS-complete, shares an important infeasibility property with other PLS-complete sets.
Supported (in part) by grants NWO/SION 612316801 and HC&M grant ERB4050PL93-0516
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
J.L. Balcázar, J. Diáz and J. Gabarró. Structural Complexity 1. Springer-Verlag, 1988.
S.T. Fischer. The Solution Sets of Local Search Problems. PhD thesis, University of Amsterdam, Department of Computer Science, Amsterdam, The Netherlands, 1995.
M. Garey and D. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, San Francisco, 1979.
D. Johnson, C. Papadimitriou, and M. Yannakakis. How easy is local search? J. Comput. System Sci., 37:79–100, 1988.
M. Krentel. Structure in Locally Optimal Solutions. Proc. 30th Annual IEEE Symposium on Foundations of Computer Science, Research Triangle Park, NC, 1989, pp 216–221.
M. Krentel. On Finding and Verifying Locally Optimal Solutions. Siam J. Comput., 19:742–749, August 1990.
C.H. Papadimitriou. The complexity of the Lin-Kernighan heuristic for the traveling salesman problem. Proc. 22nd Annual ACM Symposium on Theory of Coomputing, Baltimore, MD, 1990, pp84–94.
C.H. Papadimitriou, A.A. ShÄffer and M. Yannakakis. On the complexity of local optimality. Proc. 22nd Annual ACM Symposium on Theory of Coomputing, Baltimore, MD, 1990, pp84–94.
A.A. ShÄffer and M. Yannakakis. Simple local search problems that are hard to solve. Siam J. Comput., 20:56–87, February 1991.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1995 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Fischer, S., Torenvliet, L. (1995). The malleability of TSP 2Opt . In: Nagl, M. (eds) Graph-Theoretic Concepts in Computer Science. WG 1995. Lecture Notes in Computer Science, vol 1017. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-60618-1_73
Download citation
DOI: https://doi.org/10.1007/3-540-60618-1_73
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-60618-5
Online ISBN: 978-3-540-48487-5
eBook Packages: Springer Book Archive