Order preserving reductions and polynomial improving paths

DOI10.1016/j.orl.2005.01.003zbMath1080.90061OpenAlexW2052548200MaRDI QIDQ2583701

Derek E. Armstrong, Jacobson, Sheldon H.

Publication date: 18 January 2006

Published in: Operations Research Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.orl.2005.01.003

zbMATH Keywords

computational complexitydiscrete optimizationsatisfiabilityneighborhood functions

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Abstract computational complexity for mathematical programming problems (90C60) Combinatorial optimization (90C27)

Related Items (1)

An analysis of neighborhood functions on generic solution spaces

Cites Work

• Unnamed Item
• Unnamed Item
• Approximate solution of NP optimization problems
• Analyzing the complexity of finding good neighborhood functions for local search algorithms
• How easy is local search?
• Data-independent neighborhood functions and strict local optima
• Polynomial transformations and data-independent neighborhood functions
• On approximation scheme preserving reducibility and its applications
• Hill Climbing with Multiple Local Optima
• The effectiveness of finite improvement algorithms for finding global optima

This page was built for publication: Order preserving reductions and polynomial improving paths