TY - JOUR
T1 - Order preserving reductions and polynomial improving paths
AU - Armstrong, Derek E.
AU - Jacobson, Sheldon H.
N1 - Funding Information:
The authors wish to thank the Associate Editor, Professor Alexander Martin, and an anonymous referee for their comments and feedback on an earlier draft of the paper. All the suggested changes have resulted in a significantly improved manuscript. This research has been supported in part by the Air Force Office of Scientific Research (FA9550-04-1-0110).
Copyright:
Copyright 2008 Elsevier B.V., All rights reserved.
PY - 2006/1
Y1 - 2006/1
N2 - This paper shows that neighborhood transformations and data-independent order transformations preserve the length of improving paths and order of local optima of neighborhood functions. These results imply that finding effective neighborhood functions for Zero-One IP is at least as hard as finding effective neighborhood functions for any other NPO problem.
AB - This paper shows that neighborhood transformations and data-independent order transformations preserve the length of improving paths and order of local optima of neighborhood functions. These results imply that finding effective neighborhood functions for Zero-One IP is at least as hard as finding effective neighborhood functions for any other NPO problem.
KW - Computational complexity
KW - Discrete optimization
KW - Neighborhood functions
KW - Satisfiability
UR - http://www.scopus.com/inward/record.url?scp=28044465922&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=28044465922&partnerID=8YFLogxK
U2 - 10.1016/j.orl.2005.01.003
DO - 10.1016/j.orl.2005.01.003
M3 - Article
AN - SCOPUS:28044465922
VL - 34
SP - 9
EP - 16
JO - Operations Research Letters
JF - Operations Research Letters
SN - 0167-6377
IS - 1
ER -