TIME: 1:30-2:20 pm,  October 3, 2006

PLACE: CSE 403

TITLE:    Simply stated, what is a greedy algorithm 
             and why it may not be so simple.

SPEAKER:  Allan Borodin
          University of Toronto  (on sabbatical at University of Washington)
 

ABSTRACT:

We will try to argue why it is hard to agree on a definition of
"greedy algorithm". We present one formalism (Priority Algorithms)
which we claim models "most" greedy or greedy-like algorithms. We
consider the priority framework (and some extensions) in the context
of some well known scheduling problems, in particular, the weighted
interval scheduling problem (which has an optimal polynomial time
algorithm) and the makespan problem (which is NP hard even for the
case of uniform machines). Mainly we will indicate how much we dont
know about what should be a simple class of algorithms.