Analyzing the complexity of finding good neighborhood functions for local search algorithms

Derek E. Armstrong, Sheldon H. Jacobson

Research output: Contribution to journalArticlepeer-review


A drawback to using local search algorithms to address NP-hard discrete optimization problems is that many neighborhood functions have an exponential number of local optima that are not global optima (termed L-locals). A neighborhood function η is said to be stable if the number of L-locals is polynomial. A stable neighborhood function ensures that the number of L-locals does not grow too large as the instance size increases and results in improved performance for many local search algorithms. This paper studies the complexity of stable neighborhood functions for NP-hard discrete optimization problems by introducing neighborhood transformations. Neighborhood transformations between discrete optimization problems consist of a transformation of problem instances and a corresponding transformation of solutions that preserves the ordering imposed by the objective function values. In this paper, MAX Weighted Boolean SAT (MWBS), MAX Clause Weighted SAT (MCWS), and Zero-One Integer Programming (ZOIP) are shown to be NPO-complete with respect to neighborhood transformations. Therefore, if MWBS, MCWS, or ZOIP has a stable neighborhood function, then every problem in NPO has a stable neighborhood function. These results demonstrate the difficulty of finding effective neighborhood functions for NP-hard discrete optimization problems.

Original languageEnglish (US)
Pages (from-to)219-236
Number of pages18
JournalJournal of Global Optimization
Issue number2
StatePublished - Oct 1 2006


  • Computational complexity
  • Local search algorithms
  • NP-hard discrete optimization problems

ASJC Scopus subject areas

  • Computer Science Applications
  • Management Science and Operations Research
  • Control and Optimization
  • Applied Mathematics

Fingerprint Dive into the research topics of 'Analyzing the complexity of finding good neighborhood functions for local search algorithms'. Together they form a unique fingerprint.

Cite this