Steepest ascent can be exponential in bounded treewidth problems

DOI10.1016/J.ORL.2020.02.010MaRDI QIDQ2183191zbMATH OpenOpenAlexWikidataFDO

Authors Yanyan Li

Publication date 26 May 2020

Published in Operations Research Letters (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1911.08600, https://oatao.univ-toulouse.fr/26375/1/Cohen_26375.pdf

zbMATH Keywords

bounded treewidthlocal searchfitness landscapesteepest ascentlong pathVCSP

Mathematics Subject Classification ID

Mathematical logic and foundations (03-XX) Computer science (68-XX)

Recommendations

• Representing fitness landscapes by valued constraints to understand the complexity of local search
• On the complexity of local search in unconstrained quadratic binary optimization
• Hill Climbing with Multiple Local Optima
• Efficiency of local search with multiple local optima
• scientific article; zbMATH DE number 18531

Cites work

• Adaptation on Rugged Landscapes
• Computing equilibria: a computational complexity perspective
• Nonserial dynamic programming

Cited in

(1)

• Representing fitness landscapes by valued constraints to understand the complexity of local search

Describes a project that uses

Uses Software

• Python

This page was built for publication: Steepest ascent can be exponential in bounded treewidth problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2183191)