CS 789 THEORY SEMINAR [home]

Speaker:   Allan Borodin 
Affiliation: University of Toronto
Date:         February 16, 2004
Title:         A Model for Backtracking (And Other Thoughts on a Theory of Algorithms)

Abstract:

Many undergraduate algorithms courses and texts often organize the material in terms of ``algorithmic paradigms'', such as greedy algorithms, backtracking, dynamic programming, local search, primal-dual, etc.  We seem to be able to intuitively describe what we have in mind when we discuss these classes of algorithms but rarely (if ever) do we (or any of the standard texts) attempt to define precisely what we mean by greedy, dynamic programming, etc. 

In a paper co-authored with Nielsen and Rackoff, we proposed a definition for greedy-like (approximation) algorithms, called priority algorithms.  We did so in the context of classical scheduling problems.  Angelopoulos and Borodin then applied the priority algorithm framework to the facility location and set cover problems and Angelopoulos extended this work to randomized algorithms.  Davis and Impagliazzo have recently applied the framework to a number of traditional graph theoretic optimization problems.  For certain problems, the framework has been extended to a more general ```one-pass with revocable acceptances'' model (Bar Noy et al, Erlebach and Spieksma, Horn). 

In work with Josh Buresh Oppenheim, Avner Magen and Toni Pitassi, we extend priority and one-pass algorithms to provide a precise model for backtracking (BT algorithms) as suggested by Impagliazzo.  Similar to online and priority algorithms, we want to understand the power and limitations of BT algorithms based on the ``syntactic structure'' of the algorithm.  This BT framework is capable of modeling certain types of ``simple'' (in the sense of Woeginger) dynamic programming algorithms.  Our BT model allows a more adaptive class of algorithms.  We consider the size of a BT algorithm needed for some natural search problems relating to optimal algorithms for interval scheduling and for the simple knapsack problem, and we also consider CNF satisfiability questions.  For example, it is well known that for interval scheduling on $m$ machines, there is an optimal polynomial time simple DP algorithm where the ``dimensionality'' of the algorithm grows with $m$. Our BT lower bound shows that this growth is necessary.  For the CNF problem, 2-CNF can be solved by a polynomial size BT but for $k$ sufficiently large, there is no polynomial size BT algorithm.