OATAO - Open Archive Toulouse Archive Ouverte Open Access Week

Steepest ascent can be exponential in bounded treewidth problems

Cohen, David and Cooper, Martin C. and Kaznatcheev, Artem and Wallace, Mark Steepest ascent can be exponential in bounded treewidth problems. (2020) Operations Research Letters, 48 (3). 217-224. ISSN 0167-6377

(Document in English)

PDF (Author's version) - Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader

Official URL: https://doi.org/10.1016/j.orl.2020.02.010


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.

Item Type:Article
HAL Id:hal-02887815
Audience (journal):International peer-reviewed journal
Uncontrolled Keywords:
Institution:French research institutions > Centre National de la Recherche Scientifique - CNRS (FRANCE)
Université de Toulouse > Institut National Polytechnique de Toulouse - Toulouse INP (FRANCE)
Université de Toulouse > Université Toulouse III - Paul Sabatier - UT3 (FRANCE)
Université de Toulouse > Université Toulouse - Jean Jaurès - UT2J (FRANCE)
Université de Toulouse > Université Toulouse 1 Capitole - UT1 (FRANCE)
Other partners > Royal Holloway University of London - RHUL (UNITED KINGDOM)
Other partners > Monash University (AUSTRALIA)
Other partners > University of Oxford (UNITED KINGDOM)
Laboratory name:
Deposited On:01 Jul 2020 14:54

Repository Staff Only: item control page