Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR09-038 | 14th April 2009 00:00

Toward a Model for Backtracking and Dynamic Programming

RSS-Feed




TR09-038
Authors: Michael Alekhnovich, Allan Borodin, Joshua Buresh-Oppenheim, Russell Impagliazzo, Avner Magen
Publication: 5th May 2009 15:36
Downloads: 1601
Keywords: 


Abstract:

We propose a model called priority branching trees (pBT ) for backtracking and dynamic
programming algorithms. Our model generalizes both the priority model of Borodin, Nielson
and Rackoff, as well as a simple dynamic programming model due to Woeginger, and hence
spans a wide spectrum of algorithms. After witnessing the strength of the model, we then
show its limitations by providing lower bounds for algorithms in this model for several classical
problems such as Interval Scheduling, Knapsack and Satisfiability.



ISSN 1433-8092 | Imprint