ICS Theory Group

CompSci 269S, Fall 2007: Theory Seminar

October 19, 2007, 1:00pm, in Bren Hall 1423

Priority Algorithms

Kim S. Larsen


Most of us have an intuitive understanding of what a greedy-like algorithm is. Even though the concept has been studied in restricted scenarios, such as matroid theory, the concept, as it is used as an every-day algorithms or programming paradigm, has not been formally studied. Priority Algorithms is an attempt at modeling and capturing the power of these greedy-like algorithmic approaches to problem solving. Most of the work in the area has been targeted at establishing lower bounds on the ratios obtainable when approximating NP-hard problems using greedy-like approaches. We give a brief introduction to the topic. In the talk, we define priority algorithms, list problem scenarios that have been investigated so far, and discuss a few examples to give the flavor of the kind of argumentation which is used.

This is joint work with Allan Borodin and Joan Boyar.

On the Convergence of Upper Bound Techniques for the Average Length of Longest Common Subsequences

George Lueker


This talk will describe some methods for finding upper bounds on the expected length of two random strings of equal length, and investigate whether these methods produce bounds that are asymptotic to the true value.