Computer Science/Discrete Mathematics Seminar I

Many algorithms can intuitively be classified into one of a few basic paradigms of algorithms, such as greedy algorithms, dynamic programming, LP rounding, local search, etc. It is natural to ask which problems can be solved using these paradigms. To make such a question mathematical, we first have to formally define the paradigm. In this work (still in progress), we give such a model for dynamic programming, and compare its strength to similar models for greedy algorithms (the priority model of BNR ), backtracking (the BT model of ABBOIMP), and more limited forms of dynamic programming (Woeginger's DP-Simple model). We show that most of the classical dynamic programming algorithms fall within the DP model. For example, we show that, while the Bellman-Ford algorithm is formalizable as a DP algorithm, the shortest path problem with negative edge weights cannot be solved in sub-exponential width in the BT model even for the special case of finding longest unweighted paths in DAGs. The separation requires strong use of the fact that different paths of the Bellman-Ford algorithm view different parts of the instance graph. In contrast, we show that many natural restrictions of DP algorithms where paths at the same level view the same part of the input (FIXED or ADAPTIVE DP algorithms, as opposed to FULLY ADAPTIVE) can be simulated efficiently in the corresponding BT model. In particular, we show this for any FIXED or ADAPTIVE DP algorithm that either assigns states small integer values or uses linear functions to evaluate internal states. These two categories include almost all of the classical DP problems. We believe we can also show a lower bound for the maximum matching problem for the DP model, although this is work in progress.