2019/11/30 by David A. Cohen, Martin C. Cooper, Artem Kaznatcheev +1 · 1 citation
Computer Science · Biochemistry, Genetics and Molecular Biology · #cs.DM #cs.DS #cs.NE #q-bio.PE #msc:F.2.2 #msc:G.2.0 #msc:J.3 #acm:F.2.2 #acm:G.2.0 #acm:J.3
paper · pdf · doi:10.1016/j.orl.2020.02.010
published as Operations Research Letters 48 (2020) 217-224 · 8 pages main text, 4 pages appendix, 1 page references; fixed error in f(a,b) to match code
arxiv created 2019/12/02 · arxiv updated 2020/05/18
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.