An analysis of neighborhood functions on generic solution spaces

Derek E. Armstrong, Sheldon H. Jacobson

Research output: Contribution to journalArticlepeer-review


The effectiveness of local search algorithms on discrete optimization problems is influenced by the choice of the neighborhood function. A neighborhood function that results in all local minima being global minima is said to have zero L-locals. A polynomially sized neighborhood function with zero L-locals would ensure that at each iteration, a local search algorithm would be able to find an improving solution or conclude that the current solution is a global minimum. This paper presents a recursive relationship for computing the number of neighborhood functions over a generic solution space that results in zero L-locals. Expressions are also given for the number of tree neighborhood functions with zero L-locals. These results provide a first step towards developing expressions that are applicable to discrete optimization problems, as well as providing results that add to the collection of solved graphical enumeration problems.

Original languageEnglish (US)
Pages (from-to)529-541
Number of pages13
JournalEuropean Journal of Operational Research
Issue number2
StatePublished - Apr 16 2008


  • Discrete optimization
  • Local search
  • Neighborhood functions

ASJC Scopus subject areas

  • General Computer Science
  • Modeling and Simulation
  • Management Science and Operations Research
  • Information Systems and Management


Dive into the research topics of 'An analysis of neighborhood functions on generic solution spaces'. Together they form a unique fingerprint.

Cite this