Steepest ascent can be exponential in bounded treewidth problems

David A. Cohen, Martin C. Cooper, Artem Kaznatcheev, Mark Wallace

Research output: Contribution to journalArticleResearchpeer-review

1 Citation (Scopus)

Abstract

We investigate the complexity of local search based on steepest ascent. We show that even when all variables have domains of size two and the underlying constraint graph of variable interactions has bounded treewidth (in our construction, treewidth 7), there are fitness landscapes for which an exponential number of steps may be required to reach a local optimum. This is an improvement on prior recursive constructions of long steepest ascents, which we prove to need constraint graphs of unbounded treewidth.

Original languageEnglish
Pages (from-to)217-224
Number of pages8
JournalOperations Research Letters
Volume48
Issue number3
DOIs
Publication statusPublished - May 2020

Keywords

  • Bounded treewidth
  • Fitness landscape
  • Local search
  • Long path
  • Steepest ascent
  • VCSP

Cite this