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 -