presented by:
Joshua Buresh-Oppenheim · Sashka Davis ·
Russell Impagliazzo

---

Abstract
We define a formal model of dynamic programming algorithms which we call Prioritized Branching Programs (pBP). Our model is a generalization of the BT model of Alekhnovich et al. (IEEE Conference on Computational Complexity ,pp. 308–322, 2005), which is in turn a generalization of the priority algorithms model of Borodin, Nielson and Rack off. One of the distinguishing features of these models is that they not only capture large classes of algorithms generally considered to be greedy, backtracking or dynamic programming algorithms, but they also allow characterizations of their limitations. Hence they give meaning to the statement that a given problem can or cannot be solved by dynamic programming. After defining the model, we prove three main results: (i) that certain types of natural restrictions of our seemingly more powerful model can be simulated by the BT model; (ii) that in general our model is stronger than the BT model—a fact which is witnessed by the classical shortest paths problem; (iii) that our model has very real limitations, namely that bipartite matching cannot be efficiently computed in it, hence suggesting that here are problems that can be solved efficiently by network flow algorithms and by simple linear programming that cannot be solved by natural dynamic programming approaches.
Introduction
Formalizing algorithmic paradigms can improve our methodology as computer scientists in many ways. If we were able to say precisely what we mean by terms like greedy algorithms, dynamic programming, network flow algorithms, local-search, etc., then, when confronted with a new problem, we could hope to either find an algorithm for it by placing it in one of these models, or show that it doesn’t fit the model and move on to the next model. If a problem doesn’t fit any of our common paradigms, then it is in some sense a problem we don’t already know how to solve. From this point of view, knowing how these models relate to each other and whether they always give rise to tractible algorithms is important. Of course, this line of research can also help with our theoretical agendas. For example, it seems much easier to show that NP problems cannot be efficiently solved by common types of algorithms than it is to separate it from all of P .Much work has been conducted along these lines. Just to name a few, [16] formalized various local search paradigms, [4, 5] looked at general methods for generating linear relaxations for boolean optimization problems (specifically vertex cover), and[10] defined a general scheme for branch-and-bound algorithms and applied it toKnapsack . When it comes to dynamic programming, the body of work is particularly dense. Some of the original formalizations of dynamic programming are from Bellman [6]and Karp and Held [15]. Helman and Rosenthal, among others, refine and examine these models [13, 14, 19]. These models are extremely expressive (most problems can be formulated to fit the context), but also extremely powerful. That is, it is difficult to identify problems that can be formulated appropriately but are hard to compute. Nevertheless ,Helman and Rosenthal succeed in getting weak lower bounds for problems such as shortest directed acyclic path in staged graphs, iterated matrix multiplication and optimal binary search tree. Woeginger [20], on the other hand, defines a model called DP-simple in which only problems susceptible to a dynamic programming FPTAS can be expressed. An interesting goal is to try to maximize expressibility while maintaining a notion of computational limitation. We build on the framework established by Borodin, Nielsen and Rackoff [7],called priority algorithms, and subsequently studied and generalized by [1, 2, 8, 9,12, 17], among others. Various versions of these models succeed in capturing large classes of greedy, dynamic programming, backtracking, and primal-dual algorithms, but they also allow either impossibility results or strong complexity lower bounds to be proven for natural problems that should not intuitively fit the models. They even have the potential to make fine distinctions between related techniques, and to get tight bounds on the trade-off between resources and solution quality in their models. One modest, but lucid example comes from [2], which first made the connection between priority algorithms and dynamic programming. The best known algorithm for interval scheduling on m machines is due to [3] and uses network flow to achieve arunning time of O(n2 log n). Given the elegant and fast dynamic programming algorithm for interval scheduling on one machine, a natural question is whether dynamic programming can offer a solution for m-machines that is simpler than [3], but doesn’t sacrifice running time (or maybe even improves it). [2] prove that the complexity of any algorithm for this problem in their basic model, which captures, among many other things, the 1-machine algorithm, grows as _(nm) (as we shall see, the complexity measure of this model is fundamentally related to the number of partial solutions that need to be maintained during the course of the algorithm). This suggests that the answer to the question is no. In this paper, we introduce a new model that simulates the previous formal model of priority algorithms [7] and the BT model for backtracking and dynamic programming algorithms introduced by [2] (we rename the BT model pBT for prioritized Branching Tree, which is more suggestive of its syntactic properties and makes the connection to priority algorithms. BT originally stood for backtracking). Although a large class of dynamic programming algorithms were known to fit the pBT model, others, like the classic Bellman-Ford algorithm for the single source shortest path problem in graphs with negative weights edges, could not be seen to fit the model(and in fact, we prove here that it doesn’t, at least without some extensions). Our model , pBP, for prioritized Branching Program, is meant to capture the defining characteristics of a larger range of classical dynamic programming algorithms .Priority algorithms were defined as a formal framework for greedy algorithms. In this framework an instance is represented as a set of items. The algorithm orders the data items from the instance according to a priority function that is independent of the instance and, once it observes a data item, it has to commit to a decision which is irrevocable. For example consider the vertex cover problem. The graph can be represented as a set of data items, each one containing the name and adjacency list of one vertex. The algorithm begins with no knowledge of the contents of these items ,but it can provide a general rule for ordering the items. In each step, the top item in the ordering is revealed and the algorithm makes a decision about it (e.g. including or excluding the current vertex in the vertex cover). This decision-making process restricts the algorithm to maintain a single partial solution during its computation. The pBT model generalizes the priority framework by allowing the algorithm to maintain a tree of partial solutions. A natural measure of the complexity of a pBT algorithm is the width of its tree. Various levels of adaptivity in how the algorithm chooses its ordering rule define a hierarchy of models: fixed, adaptive and fully adaptive. [2]were able to show a variety of non-trivial lower bounds. They showed an exponential separation between the power of fixed and adaptive pBT algorithms, they also provedex ponential lower bounds for 3-SAT for the fully-adaptive model. Clearly, priority algorithms can be simulated without overhead by restricted pBT algorithms whose computation tree is a line and [2] showed a separation between width-1 and width-2algorithms.Our model, like the pBT model, maintains multiple partial solutions, but also allows memoization, which seems essential to the concept of dynamic programming. Consider the following intuitive definition [11]: “Dynamic-programming algorithms typically take advantage of overlapping sub problems by solving each subproblem once and then storing the solution in a table where it can be looked up when needed. . . . There is a variation of dynamic programming that offers the efficiency of the usual dynamic-programming approach while maintaining a top-down strategy. The idea is to memoize.” The Prioritized Branching Programs (pBP) algorithms combine the power of branching with the power of memoization. Branching allows multiple partial solutions to be maintained, while merging allows different branches of the computation to memoize the solution to common sub problems for later reuse (so in a sense pBP = BRANCH + MERGE). Any discrete optimization problem can be solved by a pBP algorithm, although possibly not an efficient one. The computation of a pBP algorithm consists of three phases. On a given input instance the algorithm generates a directed acyclic graph top-down successively as it sees more and more of the input. It then traverses the DAG bottom-up to obtain the value of the best solution it computed, and then finds the actual solution with one more top-down traversal. The number of states in the computational DAG (size) is closely related to the quality of the solution an algorithm finds. In particular, if we allow an exponential size we can solve any optimization problem. Branching was shown to give pBT algorithms extra power which separates them from priority algorithms. This raises the analogous question for pBT versus pBP. Does merging make pBP more powerful than pBT? What kind of problems can apBP algorithm solve efficiently? What are the limitations of the pBP model? These are the kinds of questions we address in our paper.

download full report
http://springerlinkindex/b373840u45215875.pdf