TY - JOUR
T1 - Data-independent neighborhood functions and strict local optima
AU - Armstrong, Derek E.
AU - Jacobson, Sheldon H.
N1 - Funding Information:
The authors would like to thank Dr. Peter L. Hammer (the Editor-in-Chief), as well as two anonymous referees for their insightful feedback and suggestions for the paper, resulting in a significantly improved manuscript. This research has been supported in part by the National Science Foundation (DMI-9907980) and the Air Force Office of Scientific Research (F49620-01-1-0007, FA9550-04-1-0110).
PY - 2005/3/15
Y1 - 2005/3/15
N2 - The paper proves that data-independent neighborhood functions with the smooth property (all strict local optima are global optima) for maximum 3-satisfiability (MAX 3-SAT) must contain all possible solutions for large instances. Data-independent neighborhood functions with the smooth property for 0-1 knapsack are shown to have size with the same order of magnitude as the cardinality of the solution space. Data-independent neighborhood functions with the smooth property for traveling salesman problem (TSP) are shown to have exponential size. These results also hold for certain polynomially solvable sub-problems of MAX 3-SAT, 0-1 knapsack and TSP.
AB - The paper proves that data-independent neighborhood functions with the smooth property (all strict local optima are global optima) for maximum 3-satisfiability (MAX 3-SAT) must contain all possible solutions for large instances. Data-independent neighborhood functions with the smooth property for 0-1 knapsack are shown to have size with the same order of magnitude as the cardinality of the solution space. Data-independent neighborhood functions with the smooth property for traveling salesman problem (TSP) are shown to have exponential size. These results also hold for certain polynomially solvable sub-problems of MAX 3-SAT, 0-1 knapsack and TSP.
KW - Computational complexity
KW - Exponential neighborhood
KW - Local search algorithm
UR - http://www.scopus.com/inward/record.url?scp=12344325734&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=12344325734&partnerID=8YFLogxK
U2 - 10.1016/j.dam.2004.09.007
DO - 10.1016/j.dam.2004.09.007
M3 - Article
AN - SCOPUS:12344325734
VL - 146
SP - 233
EP - 243
JO - Discrete Applied Mathematics
JF - Discrete Applied Mathematics
SN - 0166-218X
IS - 3
ER -