Data-independent neighborhood functions and strict local optima

DOI10.1016/j.dam.2004.09.007zbMath1077.90053MaRDI QIDQ1763477

Jacobson, Sheldon H., Derek E. Armstrong

Publication date: 22 February 2005

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2004.09.007

zbMATH Keywords

Computational complexity; Exponential neighborhood; Local search algorithm

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

90C60: Abstract computational complexity for mathematical programming problems

90C59: Approximation methods and heuristics in mathematical programming

90C27: Combinatorial optimization

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

• A survey of very large-scale neighborhood search techniques
• How easy is local search?
• Neighborhood search algorithms for guaranteeing optimal traveling salesman tours must be inefficient
• Polynomial transformations and data-independent neighborhood functions
• Hill Climbing with Multiple Local Optima
• Multiple optima in local search
• Some Examples of Difficult Traveling Salesman Problems
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item