{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,10]],"date-time":"2024-09-10T17:07:24Z","timestamp":1725988044652},"publisher-location":"Cham","reference-count":24,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319071237"},{"type":"electronic","value":"9783319071244"}],"license":[{"start":{"date-parts":[[2018,1,1]],"date-time":"2018-01-01T00:00:00Z","timestamp":1514764800000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2018]]},"DOI":"10.1007\/978-3-319-07124-4_6","type":"book-chapter","created":{"date-parts":[[2018,8,13]],"date-time":"2018-08-13T15:09:59Z","timestamp":1534172999000},"page":"299-339","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Theory of Local Search"],"prefix":"10.1007","author":[{"given":"W.","family":"Michiels","sequence":"first","affiliation":[]},{"given":"E. H. L.","family":"Aarts","sequence":"additional","affiliation":[]},{"given":"J.","family":"Korst","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2018,8,14]]},"reference":[{"key":"6_CR1","doi-asserted-by":"crossref","unstructured":"Angel E, Christopoulos P, Zissimopoulos V (2014) Local search: complexity and approximation. In: Paschos VT (ed) Paradigms of combinatorial optimization: problems and new approaches, vol 2. Wiley, Hoboken, pp 435\u2013471","DOI":"10.1002\/9781119005353.ch14"},{"key":"6_CR2","doi-asserted-by":"crossref","unstructured":"Chandra B, Karloff H, Tovey C (1999) New results on the old k-opt algorithm for the traveling salesman problem. SIAM J Comput 28:1998\u20132029","DOI":"10.1137\/S0097539793251244"},{"key":"6_CR3","unstructured":"Christofides N (1976) Worst-case analysis of a new heuristic for the traveling salesman problem. Technical report, 388. Graduate School of Industrial Administration, Carnegie-Mellon University, Pittsburgh"},{"key":"6_CR4","unstructured":"Englert M, R\u00f6glin H, V\u00f6cking B (2007) Worst case and probabilistic analysis of the 2-opt algorithm for the TSP. In: Proceedings of the 18th ACM-SIAM symposium on discrete algorithm, New Orleans, pp 1295\u20131304"},{"key":"6_CR5","doi-asserted-by":"crossref","unstructured":"Fearnley J, Savani R (2015) The complexity of the simplex method. In: Proceedings of the forty-seventh annual ACM symposium on theory of computing, pp 201\u2013208","DOI":"10.1145\/2746539.2746558"},{"key":"6_CR6","doi-asserted-by":"crossref","unstructured":"Fischer S (1995) A note on the complexity of local search problems. Inf Process Lett 53:69\u201375","DOI":"10.1016\/0020-0190(94)00184-Z"},{"key":"6_CR7","unstructured":"Gordon S (2017) The complexity of continuous local search. Master thesis, University of Illinois"},{"key":"6_CR8","doi-asserted-by":"crossref","unstructured":"Guo J, Hartung S, Niedermeier R, Such\u00fd O (2013) The parameterized complexity of local search for TSP, more refined. Algorithmica 67:89\u2013110","DOI":"10.1007\/s00453-012-9685-8"},{"key":"6_CR9","doi-asserted-by":"crossref","unstructured":"Hansen P, Jaumard B (1990) Algorithms for the maximum satisfiability problem. Computing 44:279\u2013303","DOI":"10.1007\/BF02241270"},{"key":"6_CR10","unstructured":"Johnson D, McGeoch L (1997) The traveling salesman problem: a case study. In: Aarts E, Lenstra J (eds) Local search in combinatorial optimization. Wiley, New York, pp 215\u2013310"},{"key":"6_CR11","doi-asserted-by":"crossref","unstructured":"Johnson D, Papadimitriou C, Yannakakis M (1988) How easy is local search? J Comput Syst Sci 37:79\u2013100","DOI":"10.1016\/0022-0000(88)90046-3"},{"key":"6_CR12","doi-asserted-by":"crossref","unstructured":"Khanna S, Motwani R, Sudan M, Vazirani U (1998) On syntactic versus computational views of approximability. SIAM J Comput 28:164\u2013191","DOI":"10.1137\/S0097539795286612"},{"key":"6_CR13","doi-asserted-by":"crossref","unstructured":"Levin A, Yovel U (2013) Nonoblivious 2-Opt heuristics for the traveling salesman problem. Networks 62(3):201\u2013219","DOI":"10.1002\/net.21512"},{"key":"6_CR14","unstructured":"Luecker G (1976) unpublished manuscript. Department of Computer Science, Princeton University, Princeton"},{"key":"6_CR15","doi-asserted-by":"crossref","unstructured":"Marx D (2008) Searching the k-change neighborhood for TSP is w[1]-hard. Oper Res Lett 36:31\u201336","DOI":"10.1016\/j.orl.2007.02.008"},{"key":"6_CR16","unstructured":"Michiels W, Aarts E, Korst J (2007) Theoretical aspects of local search. Springer, Berlin"},{"key":"6_CR17","doi-asserted-by":"crossref","unstructured":"Monien B, Dumrauf D, Tscheuschner T (2010) Local search: simple, successful, but sometimes sluggish. In: Automata, languages and programming, pp 1\u201317","DOI":"10.1007\/978-3-642-14165-2_1"},{"key":"6_CR18","doi-asserted-by":"publisher","first-page":"1201","DOI":"10.1137\/S0097539703431007","volume":"33","author":"J Orlin","year":"2004","unstructured":"Orlin J, Punnen A, Schulz A (2004) Approximate local search in combinatorial optimization. SIAM J Comput 33:1201\u20131214","journal-title":"SIAM J Comput"},{"key":"6_CR19","doi-asserted-by":"publisher","first-page":"15881","DOI":"10.1073\/pnas.1416954111","volume":"111","author":"C Papadimitriou","year":"2014","unstructured":"Papadimitriou C (2014) Algorithms, complexity, and the sciences. Proc Natl Acad Sci 111:15881\u201315887","journal-title":"Proc Natl Acad Sci"},{"key":"6_CR20","doi-asserted-by":"publisher","first-page":"76","DOI":"10.1137\/0206005","volume":"6","author":"C Papadimitriou","year":"1977","unstructured":"Papadimitriou C, Steiglitz K (1977) On the complexity of local search for the traveling salesman problem. SIAM J Comput 6:76\u201383","journal-title":"SIAM J Comput"},{"key":"6_CR21","volume-title":"Combinatorial optimization","author":"C Papadimitriou","year":"1982","unstructured":"Papadimitriou C, Steiglitz K (1982) Combinatorial optimization. Prentice-Hall, Englewood Cliffs"},{"key":"6_CR22","doi-asserted-by":"publisher","first-page":"555","DOI":"10.1145\/321958.321975","volume":"23","author":"S Sahni","year":"1976","unstructured":"Sahni S, Gonzalez T (1976) P-complete approximation problems. J Assoc Comput Mach 23:555\u2013565","journal-title":"J Assoc Comput Mach"},{"key":"6_CR23","doi-asserted-by":"crossref","unstructured":"Schulz A, Weismantel R, Ziegler G (1995) 0\/1-integer programming: optimization and augmentation are equivalent. In: Proceedings of the 3rd annual European symposium on algorithms, Corfu, pp 473\u2013483","DOI":"10.1007\/3-540-60313-1_164"},{"key":"6_CR24","first-page":"19","volume-title":"Local search in combinatorial optimization","author":"M Yannakakis","year":"1997","unstructured":"Yannakakis M (1997) Computational complexity. In: Aarts E, Lenstra J (eds) Local search in combinatorial optimization. Wiley, New York, pp 19\u201355"}],"container-title":["Handbook of Heuristics"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-07124-4_6","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,10,22]],"date-time":"2019-10-22T03:20:18Z","timestamp":1571714418000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-07124-4_6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018]]},"ISBN":["9783319071237","9783319071244"],"references-count":24,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-07124-4_6","relation":{},"subject":[],"published":{"date-parts":[[2018]]}}}