Analyzing the complexity of finding good neighborhood functions for local search algorithms
From MaRDI portal
Publication:857808
DOI10.1007/s10898-006-9007-2zbMath1114.90164OpenAlexW2068598433MaRDI QIDQ857808
Derek E. Armstrong, Jacobson, Sheldon H.
Publication date: 5 January 2007
Published in: Journal of Global Optimization (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s10898-006-9007-2
Analysis of algorithms (68W40) Abstract computational complexity for mathematical programming problems (90C60) Search theory (90B40) Approximation methods and heuristics in mathematical programming (90C59)
Related Items
Polynomial transformations and data-independent neighborhood functions ⋮ An analysis of neighborhood functions on generic solution spaces ⋮ Order preserving reductions and polynomial improving paths
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Approximate solution of NP optimization problems
- Local search, reducibility and approximability of NP-optimization problems
- How easy is local search?
- Structure preserving reductions among convex optimization problems
- Optimization, approximation, and complexity classes
- Complexity of uniqueness and local search in quadratic 0-1 programming
- Studying the complexity of global verification for NP-hard discrete optimization problems
- On complexity of unconstrained hyperbolic 0--1 programming problems
- Polynomial transformations and data-independent neighborhood functions
- On approximation scheme preserving reducibility and its applications
- Multiple optima in local search
- The effectiveness of finite improvement algorithms for finding global optima
- The complexity of theorem-proving procedures
