## CompSci 269S, Fall 2007: Theory Seminar

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

# Priority Algorithms

## Kim S. Larsen

Abstract:

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.

## George Lueker

Abstract:

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.