Skip to main content
main-content
Top

Hint

Swipe to navigate through the chapters of this book

2018 | OriginalPaper | Chapter

11. Theory of Local Search

Authors: W. Michiels, E. H. L. Aarts, J. Korst

Published in: Handbook of Heuristics

Publisher: Springer International Publishing

share
SHARE

Abstract

Local search is a widely used method to solve combinatorial optimization problems. As many relevant combinatorial optimization problems are NP-hard, we often may not expect to find an algorithm that is guaranteed to return an optimal solution in a reasonable amount of time, i.e., in polynomial time. Therefore, one often resorts to heuristic methods that return good, suboptimal solutions in reasonable running times. Local search is a heuristic method that is popular for its ability to trade solution quality against computation time. By spending more time, we will generally get better solutions. Well-known examples of local search approaches are iterative improvement, simulated annealing, and tabu search.
The performance of local search, in terms of quality or running time, may be investigated empirically, probabilistically, and from a worst-case perspective. In this chapter we focus on the last option. That is, we give provable results on the worst-case performance of local search algorithms.
Besides combinatorial optimization problems, the theory discussed in this chapter also finds its application in game theory and computational complexity.
Literature
1.
go back to reference 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–471 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–471
2.
go back to reference 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–2029 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–2029
3.
go back to reference 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 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
4.
go back to reference Englert M, Röglin H, Vöcking B (2007) Worst case and probabilistic analysis of the 2-opt algorithm for the TSP. In: Proceedings of the 18 th ACM-SIAM symposium on discrete algorithm, New Orleans, pp 1295–1304 Englert M, Röglin H, Vöcking B (2007) Worst case and probabilistic analysis of the 2-opt algorithm for the TSP. In: Proceedings of the 18 th ACM-SIAM symposium on discrete algorithm, New Orleans, pp 1295–1304
5.
go back to reference 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–208 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–208
6.
go back to reference Fischer S (1995) A note on the complexity of local search problems. Inf Process Lett 53:69–75 Fischer S (1995) A note on the complexity of local search problems. Inf Process Lett 53:69–75
7.
go back to reference Gordon S (2017) The complexity of continuous local search. Master thesis, University of Illinois Gordon S (2017) The complexity of continuous local search. Master thesis, University of Illinois
8.
go back to reference Guo J, Hartung S, Niedermeier R, Suchý O (2013) The parameterized complexity of local search for TSP, more refined. Algorithmica 67:89–110 Guo J, Hartung S, Niedermeier R, Suchý O (2013) The parameterized complexity of local search for TSP, more refined. Algorithmica 67:89–110
9.
go back to reference Hansen P, Jaumard B (1990) Algorithms for the maximum satisfiability problem. Computing 44:279–303 Hansen P, Jaumard B (1990) Algorithms for the maximum satisfiability problem. Computing 44:279–303
10.
go back to reference 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–310 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–310
11.
go back to reference Johnson D, Papadimitriou C, Yannakakis M (1988) How easy is local search? J Comput Syst Sci 37:79–100 Johnson D, Papadimitriou C, Yannakakis M (1988) How easy is local search? J Comput Syst Sci 37:79–100
12.
go back to reference Khanna S, Motwani R, Sudan M, Vazirani U (1998) On syntactic versus computational views of approximability. SIAM J Comput 28:164–191 Khanna S, Motwani R, Sudan M, Vazirani U (1998) On syntactic versus computational views of approximability. SIAM J Comput 28:164–191
13.
go back to reference Levin A, Yovel U (2013) Nonoblivious 2-Opt heuristics for the traveling salesman problem. Networks 62(3):201–219 Levin A, Yovel U (2013) Nonoblivious 2-Opt heuristics for the traveling salesman problem. Networks 62(3):201–219
14.
go back to reference Luecker G (1976) unpublished manuscript. Department of Computer Science, Princeton University, Princeton Luecker G (1976) unpublished manuscript. Department of Computer Science, Princeton University, Princeton
15.
go back to reference Marx D (2008) Searching the k-change neighborhood for TSP is w[1]-hard. Oper Res Lett 36:31–36 Marx D (2008) Searching the k-change neighborhood for TSP is w[1]-hard. Oper Res Lett 36:31–36
16.
go back to reference Michiels W, Aarts E, Korst J (2007) Theoretical aspects of local search. Springer, Berlin Michiels W, Aarts E, Korst J (2007) Theoretical aspects of local search. Springer, Berlin
17.
go back to reference Monien B, Dumrauf D, Tscheuschner T (2010) Local search: simple, successful, but sometimes sluggish. In: Automata, languages and programming, pp 1–17 Monien B, Dumrauf D, Tscheuschner T (2010) Local search: simple, successful, but sometimes sluggish. In: Automata, languages and programming, pp 1–17
18.
go back to reference Orlin J, Punnen A, Schulz A (2004) Approximate local search in combinatorial optimization. SIAM J Comput 33:1201–1214 MathSciNetCrossRef Orlin J, Punnen A, Schulz A (2004) Approximate local search in combinatorial optimization. SIAM J Comput 33:1201–1214 MathSciNetCrossRef
19.
go back to reference Papadimitriou C (2014) Algorithms, complexity, and the sciences. Proc Natl Acad Sci 111:15881–15887 CrossRef Papadimitriou C (2014) Algorithms, complexity, and the sciences. Proc Natl Acad Sci 111:15881–15887 CrossRef
20.
go back to reference Papadimitriou C, Steiglitz K (1977) On the complexity of local search for the traveling salesman problem. SIAM J Comput 6:76–83 MathSciNetCrossRef Papadimitriou C, Steiglitz K (1977) On the complexity of local search for the traveling salesman problem. SIAM J Comput 6:76–83 MathSciNetCrossRef
21.
go back to reference Papadimitriou C, Steiglitz K (1982) Combinatorial optimization. Prentice-Hall, Englewood Cliffs MATH Papadimitriou C, Steiglitz K (1982) Combinatorial optimization. Prentice-Hall, Englewood Cliffs MATH
23.
go back to reference 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–483 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–483
24.
go back to reference Yannakakis M (1997) Computational complexity. In: Aarts E, Lenstra J (eds) Local search in combinatorial optimization. Wiley, New York, pp 19–55 Yannakakis M (1997) Computational complexity. In: Aarts E, Lenstra J (eds) Local search in combinatorial optimization. Wiley, New York, pp 19–55
Metadata
Title
Theory of Local Search
Authors
W. Michiels
E. H. L. Aarts
J. Korst
Copyright Year
2018
DOI
https://doi.org/10.1007/978-3-319-07124-4_6

Premium Partner