Get our free extension to see links to code for papers anywhere online!Free add-on: code for papers everywhere!Free add-on: See code for papers anywhere!
Add to Chrome
Add to Firefox
Add to EdgeSteepest ascent can be exponential in bounded treewidth problems
Nov 19, 2019
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 (graph of variable interactions) has bounded treewidth (in our construction, treewidth is 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.
* 8 pages main text, 4 pages appendix, 1 page references
View paper on