TY - JOUR
T1 - Polynomial transformations and data-independent neighborhood functions
AU - Armstrong, Derek E.
AU - Jacobson, Sheldon H.
N1 - Funding Information:
This research is supported in part by the National Science Foundation (DMI-9907980) and the Air Force Office of Scientific Research (FA9550-04-1-0110, F49620-01-1-0007, F49620-98-1-0111).
PY - 2004/9/30
Y1 - 2004/9/30
N2 - A neighborhood function that is polynomial in size and independent of the problem data, except that it may depend on the maximum absolute value of a number in an instance, is termed semi-reasonable. A semi-data-independent order transformation (SDIOT) is introduced such that if problem A SDIOT to problem B and B has a semi-reasonable neighborhood function, where the number of local optima is polynomial, then problem A has a semi-reasonable neighborhood function such that the number of local optima is polynomial. A large class of optimization problems is shown to SDIOT to Maximum Clause Weighted Satisfiability.
AB - A neighborhood function that is polynomial in size and independent of the problem data, except that it may depend on the maximum absolute value of a number in an instance, is termed semi-reasonable. A semi-data-independent order transformation (SDIOT) is introduced such that if problem A SDIOT to problem B and B has a semi-reasonable neighborhood function, where the number of local optima is polynomial, then problem A has a semi-reasonable neighborhood function such that the number of local optima is polynomial. A large class of optimization problems is shown to SDIOT to Maximum Clause Weighted Satisfiability.
KW - Computational complexity
KW - Local search algorithm
KW - NP-hard discrete optimization problem
UR - http://www.scopus.com/inward/record.url?scp=4243158417&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=4243158417&partnerID=8YFLogxK
U2 - 10.1016/j.dam.2003.06.008
DO - 10.1016/j.dam.2003.06.008
M3 - Article
AN - SCOPUS:4243158417
SN - 0166-218X
VL - 143
SP - 272
EP - 284
JO - Discrete Applied Mathematics
JF - Discrete Applied Mathematics
IS - 1-3
ER -