Polynomial transformations and data-independent neighborhood functions

Derek E. Armstrong, Sheldon H. Jacobson

Research output: Contribution to journalArticlepeer-review


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.

Original languageEnglish (US)
Pages (from-to)272-284
Number of pages13
JournalDiscrete Applied Mathematics
Issue number1-3
StatePublished - Sep 30 2004


  • Computational complexity
  • Local search algorithm
  • NP-hard discrete optimization problem

ASJC Scopus subject areas

  • Discrete Mathematics and Combinatorics
  • Applied Mathematics


Dive into the research topics of 'Polynomial transformations and data-independent neighborhood functions'. Together they form a unique fingerprint.

Cite this