Data-independent neighborhood functions and strict local optima

Derek E. Armstrong, Sheldon H. Jacobson

Research output: Contribution to journalArticlepeer-review

Abstract

The paper proves that data-independent neighborhood functions with the smooth property (all strict local optima are global optima) for maximum 3-satisfiability (MAX 3-SAT) must contain all possible solutions for large instances. Data-independent neighborhood functions with the smooth property for 0-1 knapsack are shown to have size with the same order of magnitude as the cardinality of the solution space. Data-independent neighborhood functions with the smooth property for traveling salesman problem (TSP) are shown to have exponential size. These results also hold for certain polynomially solvable sub-problems of MAX 3-SAT, 0-1 knapsack and TSP.

Original languageEnglish (US)
Pages (from-to)233-243
Number of pages11
JournalDiscrete Applied Mathematics
Volume146
Issue number3
DOIs
StatePublished - Mar 15 2005

Keywords

  • Computational complexity
  • Exponential neighborhood
  • Local search algorithm

ASJC Scopus subject areas

  • Discrete Mathematics and Combinatorics
  • Applied Mathematics

Fingerprint Dive into the research topics of 'Data-independent neighborhood functions and strict local optima'. Together they form a unique fingerprint.

Cite this