Harvard Theory of Computation Seminar

Towards Models for Backtracking and Dynamic Programming

Josh Buresh-Oppenheim, Simon Fraser University, Canada

Place and Time: FRIDAY 10/6, Maxwell Dworkin 319 Refreshments at 10:30am, talk at 10:45am

ABSTRACT

Since most algorithms that people use can intuitively be classified into large paradigms of algorithms such as greedy, dynamic programming, linear and semidefinite programming, local search, etc., it is natural to ask what problems can be computed by these paradigms. This question can be seen as an alternative to asking what problems can be computed by all, say, poly-time algorithms in that the restriction on the algorithms is more conceptual rather than complexity-theoretic. Of course, to ask a question about an algorithmic paradigm, you first have to formally define the paradigm. We offer one very natural model, pBT, which captures many algorithms generally considered to be dynamic programming or backtracking. This model is an extension of the Priority Algorithm model of Borodin, Nielsen and Rackoff, which captures greedy algorithms. We demonstrate many upper and lower bounds in this model for problems such as interval scheduling, knapsack and SAT. We then define a stronger model, pBP, and show that it seems to capture some aspects of dynamic programming that pBT does not, but still does not solve even tractable problems that do not intuitively have dynamic programming algorithms.

This is joint work with Mikhail Alekhnovich, Allan Borodin, Sashka Davis, Russell Impagliazzo, Avner Magen and Toni Pitassi.