Steepest ascent can be exponential in bounded treewidth problems

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

doi:10.1016/j.orl.2020.02.010

Steepest ascent can be exponential in bounded treewidth problems

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

Department of Data Science & AI

Research output: Contribution to journal › Article › Research › peer-review

2 Citations (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 language	English
Pages (from-to)	217-224
Number of pages	8
Journal	Operations Research Letters
Volume	48
Issue number	3
DOIs	https://doi.org/10.1016/j.orl.2020.02.010
Publication status	Published - May 2020

Keywords

Bounded treewidth
Fitness landscape
Local search
Long path
Steepest ascent
VCSP

Access to Document

10.1016/j.orl.2020.02.010

Cite this

@article{06f9f8097bdd4c7988de2ea4c69507a0,

title = "Steepest ascent can be exponential in bounded treewidth problems",

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.",

keywords = "Bounded treewidth, Fitness landscape, Local search, Long path, Steepest ascent, VCSP",

author = "Cohen, {David A.} and Cooper, {Martin C.} and Artem Kaznatcheev and Mark Wallace",

year = "2020",

month = may,

doi = "10.1016/j.orl.2020.02.010",

language = "English",

volume = "48",

pages = "217--224",

journal = "Operations Research Letters",

issn = "0167-6377",

publisher = "Elsevier",

number = "3",

}

TY - JOUR

T1 - Steepest ascent can be exponential in bounded treewidth problems

AU - Cohen, David A.

AU - Cooper, Martin C.

AU - Kaznatcheev, Artem

AU - Wallace, Mark

PY - 2020/5

Y1 - 2020/5

N2 - 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.

AB - 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.

KW - Bounded treewidth

KW - Fitness landscape

KW - Local search

KW - Long path

KW - Steepest ascent

KW - VCSP

UR - http://www.scopus.com/inward/record.url?scp=85081168183&partnerID=8YFLogxK

U2 - 10.1016/j.orl.2020.02.010

DO - 10.1016/j.orl.2020.02.010

M3 - Article

AN - SCOPUS:85081168183

SN - 0167-6377

VL - 48

SP - 217

EP - 224

JO - Operations Research Letters

JF - Operations Research Letters

IS - 3

ER -

Steepest ascent can be exponential in bounded treewidth problems

Abstract

Keywords

Access to Document

Other files and links

Cite this