Analyzing the complexity of finding good neighborhood functions for local search algorithms

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

zbMATH Keywords

Computational complexityLocal search algorithmsNP-hard discrete optimization problems

Mathematics Subject Classification ID

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