Steepest ascent can be exponential in bounded treewidth problems

DOI10.1016/J.ORL.2020.02.010OpenAlexW2990526839WikidataQ115568194 ScholiaQ115568194MaRDI QIDQ2183191FDOQ2183191

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

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

zbMATH Keywords

bounded treewidthlocal searchfitness landscapesteepest ascentlong pathVCSP

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (1)

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

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)