Article

Toward a Model for Backtracking and Dynamic Programming

Authors:

Michael Alekhnovich,

Allan Borodin,

Joshua Buresh-Oppenheim,

Russell Impagliazzo,

Avner Magen,

Toniann PitassiAuthors Info & Claims

CCC '05: Proceedings of the 20th Annual IEEE Conference on Computational Complexity

Pages 308 - 322

https://doi.org/10.1109/CCC.2005.32

Published: 11 June 2005 Publication History

Publisher Site

Abstract

We consider a model (BT) for backtracking 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 andsatisfiability.

Cited By

View all

Buresh-Oppenheim JDavis SImpagliazzo R(2011)A Stronger Model of Dynamic Programming AlgorithmsAlgorithmica10.5555/3118756.311901660:4(938-968)Online publication date: 1-Aug-2011
https://dl.acm.org/doi/10.5555/3118756.3119016
Borodin ACashman DMagen A(2011)How well can primal-dual and local-ratio algorithms perform?ACM Transactions on Algorithms10.1145/1978782.19787847:3(1-26)Online publication date: 15-Jul-2011
https://dl.acm.org/doi/10.1145/1978782.1978784
Beame PImpagliazzo RPitassi TSegerlind N(2010)Formula Caching in DPLLACM Transactions on Computation Theory10.1145/1714450.17144521:3(1-33)Online publication date: 1-Mar-2010
https://dl.acm.org/doi/10.1145/1714450.1714452
Show More Cited By

Index Terms

Toward a Model for Backtracking and Dynamic Programming
1. Theory of computation
  1. Design and analysis of algorithms
    1. Algorithm design techniques
      1. Backtracking
      2. Dynamic programming

Recommendations

Toward a Model for Backtracking and Dynamic Programming

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, ...
Parallel Dynamic Programming

Recurrence formulations for various problems, such as finding an optimal order of matrixmultiplication, finding an optimal binary search tree, and optimal triangulation of polygons, assume a similar form. A. Gibbons and W. Rytter (1988) gave a CREW PRAM ...
Efficient Backtracking Instruction Schedulers
PACT '00: Proceedings of the 2000 International Conference on Parallel Architectures and Compilation Techniques

Current schedulers for acyclic regions schedule operations in dependence order and never undo a scheduling decision. In contrast, backtracking schedulers may unschedule operations and can often generate better schedules. In this paper, we describe a ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

CCC '05: Proceedings of the 20th Annual IEEE Conference on Computational Complexity

June 2005

335 pages

ISBN:0769523641

Publisher

IEEE Computer Society

United States

Publication History

Published: 11 June 2005

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

11
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 19 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Buresh-Oppenheim JDavis SImpagliazzo R(2011)A Stronger Model of Dynamic Programming AlgorithmsAlgorithmica10.5555/3118756.311901660:4(938-968)Online publication date: 1-Aug-2011
https://dl.acm.org/doi/10.5555/3118756.3119016
Borodin ACashman DMagen A(2011)How well can primal-dual and local-ratio algorithms perform?ACM Transactions on Algorithms10.1145/1978782.19787847:3(1-26)Online publication date: 15-Jul-2011
https://dl.acm.org/doi/10.1145/1978782.1978784
Beame PImpagliazzo RPitassi TSegerlind N(2010)Formula Caching in DPLLACM Transactions on Computation Theory10.1145/1714450.17144521:3(1-33)Online publication date: 1-Mar-2010
https://dl.acm.org/doi/10.1145/1714450.1714452
Angelopoulos SBorodin A(2010)Randomized priority algorithmsTheoretical Computer Science10.1016/j.tcs.2010.03.014411:26-28(2542-2558)Online publication date: 1-Jun-2010
https://dl.acm.org/doi/10.1016/j.tcs.2010.03.014
Li XLiu T(2010)On exponential time lower bound of Knapsack under backtrackingTheoretical Computer Science10.1016/j.tcs.2009.12.004411:16-18(1883-1888)Online publication date: 1-Mar-2010
https://dl.acm.org/doi/10.1016/j.tcs.2009.12.004
Borodin ABoyar JLarsen KMirmohammadi N(2010)Priority algorithms for graph optimization problemsTheoretical Computer Science10.1016/j.tcs.2009.09.033411:1(239-258)Online publication date: 1-Jan-2010
https://dl.acm.org/doi/10.1016/j.tcs.2009.09.033
Halman NKlabjan DLi COrlin JSimchi-Levi DTeng S(2008)Fully polynomial time approximation schemes for stochastic dynamic programsProceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms10.5555/1347082.1347159(700-709)Online publication date: 20-Jan-2008
https://dl.acm.org/doi/10.5555/1347082.1347159
Williams R(2008)Applying practice to theoryACM SIGACT News10.1145/1466390.146640139:4(37-52)Online publication date: 30-Nov-2008
https://dl.acm.org/doi/10.1145/1466390.1466401
Li XLiu TPeng HQian LSun HXu JXu KZhu J(2007)Improved exponential time lower bound of Knapsack problem under BT modelProceedings of the 4th international conference on Theory and applications of models of computation10.5555/1767854.1767913(624-631)Online publication date: 22-May-2007
https://dl.acm.org/doi/10.5555/1767854.1767913
Borodin A(2006)Further reflections on a theory for basic algorithmsProceedings of the Second international conference on Algorithmic Aspects in Information and Management10.1007/11775096_1(1-9)Online publication date: 20-Jun-2006
https://dl.acm.org/doi/10.1007/11775096_1
Show More Cited By

Abstract

Cited By

Index Terms

Recommendations