Computer Science/Discrete Mathematics Seminar II

In part I of this talk, we began a discussion of "simple algorithms" and restricted our attention to the priority algorithm model which models ``greedy-like'' algorithms. In Part II of this talk, we will extend the priority algorithm framework to obtain models for other simple classes of algorithms. In particular, we define the "priority branching tree" pBT model so as to model a class of simple dynamic programming (in the terminology of Woeginger) and simple backtracking algorithms. We also define priority stack algorithm so as to model some simple classes of primal dual/local ratio algorithms. More specifically, the pBT model allows us to model the dynamic programming algorithms used for problems such as weighted interval scheduling, other special cases of the time constrained scheduling problem, the knapsack problem, and the edit distance problem. The pBT framework also models various DPLL algorithms for solving satisfiability. The stack model provides an alternative way to solve weighted interval scheduling and other bandwidth allocation problems. It also models a primal dual algorithm for Steiner trees. We will start with a review of the priority algorithm model so that this talk will be self-contained.