Theoretical aspects of local search.
type: Item
instance of: scholarly article
title: Theoretical aspects of local search.
zbMATH Open document ID: 1130.90061
DOI: 10.1007/978-3-540-35854-1
author: W. Michiels
author: E. Aarts
author: J. Korst
published in: Monographs in Theoretical Computer Science. An EATCS Series
publication date: 2007-01-18T00:00:00Z
review text: For 50 years, local search methods have been very successfully applied to large scale combinatorial optimization problems arising in real world situations. While the vast majority of the literature reports on experimental results with local search strategies applied to specific problems, this book focuses on theoretical aspects, in mainly three areas: -- performance guarantees, -- time complexity, -- asymptotic convergence. Throughout the book, the authors use exemplary problems such as the TSP and scheduling problems for which they prove results relating to the above topics. In Chapter 1 the authors give the fundamental definitions to positions local search within combinatorial optimization. In Chapter 2 examples of local search algorithms are given, starting, one might say of course, with \(k\)-change for the travelling salesman problem (TSP). The other example problems are machine scheduling, the Steiner Tree Problem on graphs, graph coloring and stable configuration in Hopfield networks. In Chapter 3 the authors discuss indirect representation of solutions, i.e. by features such that for any value of that feature a best solution with that value is identifiable in polynomial time. Some examples from scheduling are given. In Chapter 4 properties of neighborhood functions are discussed, in particular the diameter and connectivity of neighborhood graphs for TSP and scheduling. In Chapters 5 and 6 the authors proceed to the main results in the first two areas mentioned above. Chapter 5 addresses the performance guarantees for local search algorithms, i.e. worst case analysis. First, the authors discuss exact neighborhood functions, (for which every local optimum is global, e.g. conditions for exactness of \(k\)-change for TSP) then performance ratios (again for \(k\)-change for TSP but also move and swap in scheduling) followed by non-approximability results, and how for certain problems neighborhood functions lead to polynomial time algorithms. In Chapter 6, the com…
reviewed by: Matthias Ehrgott
Mathematics Subject Classification ID: 90C59
Mathematics Subject Classification ID: 90-02
Mathematics Subject Classification ID: 90B35
Mathematics Subject Classification ID: 90C27
Mathematics Subject Classification ID: 90C35
Mathematics Subject Classification ID: 90C60
Mathematics Subject Classification ID: 90B40
zbMATH DE Number: 5116415
zbMATH Keywords: Local search
zbMATH Keywords: complexity
zbMATH Keywords: approximation algorithm
zbMATH Keywords: travelling salesman problem
zbMATH Keywords: machine scheduling
MaRDI profile type: Publication
full work available at URL: https://doi.org/10.1007/978-3-540-35854-1
OpenAlex ID: W1539964999
description: scientific article; zbMATH DE number 5116415