UC San Diego

This dissertation formalizes the intuitive notion of the basic algorithmic paradigms. We present three formal models which aim to capture the intrinsic power of greedy, backtracking and dynamic programming algorithms. We develop lower bound techniques for proving negative results for all algorithms in all models, which allow us to make strong statements about the limitations of each paradigm. Borodin et al. (2003) designed the Priority algorithms, a formal model of greedy algorithms for scheduling problems. We generalized the priority model to arbitrary problem domain and in particular graph problems and develop a lower bound technique for proving negative results for the class of all priority algorithms. We use the lower bound technique to show that finding shortest path in graphs with negative weights cannot be solved by a priority algorithm. We also prove that Dijkstra's algorithm is inherently adaptive and cannot be made non- adaptive. We show inapproximability results within the model for minimum weighted vertex cover, minimum metric Steiner tree, and maximum independent set problems. We develop a new 1.8-approximation scheme for the Steiner(1, 2) problem. Alekhnovich et al. (2005) presented a model of backtracking and dynamic programming algorithms called prioritized Branching Trees (pBT). We generalize their model to allow free branching and call this new model prioritized Free Branching Tree (pFBT) algorithms and developed a lower bound technique for proving negative results for randomized priority algorithms, pBT and pFBT algorithms. We use the technique to prove that pBT algorithms require exponential width to solve the 7-SAT problem and that pFBT algorithms require width of 2̂(\sqrt }n})} to solve the 7-SAT problem.Bellman-Ford is a classical dynamic programming algorithm and we show that pBT algorithms require width of 2̂}\Omega(n̂}1/9})} to solve the shortest path problem in graphs with negative weights exactly. Next we develop a stronger model of dynamic programming algorithms called prioritized Branching Programs (pBP). pBP algorithms can simulate pBT algorithms at no additional cost but also capture the notion of memoization which we believe is an essential part of the dynamic programming paradigm. We show that this class of algorithms can solve the shortest paths in graphs with negative weights but no negative cycles efficiently. We also show that two pBP sub-models can be simulated by pBT algorithms