Order preserving reductions and polynomial improving paths

DOI10.1016/J.ORL.2005.01.003MaRDI QIDQ2583701zbMATH OpenOpenAlexFDO

Authors Derek E. Armstrong, Sheldon H. Jacobson

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 complexitysatisfiabilitydiscrete optimizationneighborhood functions

Mathematics Subject Classification ID

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

Recommendations

• Polynomial transformations and data-independent neighborhood functions
• Data-independent neighborhood functions and strict local optima
• Integer Programming: Optimization and Evaluation Are Equivalent
• Zu einigen Nachbarschaftsstrukturen fiir Iterationsverfahren zur naherangsweisen Lösung spezieller Reihenfolgeprohleme
• Approximation preserving reductions

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 3793772 (Why is no real title available?)
• Analyzing the complexity of finding good neighborhood functions for local search algorithms
• Approximate solution of NP optimization problems
• Data-independent neighborhood functions and strict local optima
• Hill Climbing with Multiple Local Optima
• How easy is local search?
• On approximation scheme preserving reducibility and its applications
• Polynomial transformations and data-independent neighborhood functions
• The effectiveness of finite improvement algorithms for finding global optima

Cited in

(3)

• An improved general path order
• An analysis of neighborhood functions on generic solution spaces
• Polynomial transformations and data-independent neighborhood functions

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2583701)