Title: Simple Algorithms for Simple Problems and Why It Isn't So Simple
Speaker: Allan Borodin, University of Toronto and IAS
Date: Wednesday, May 2, 2007 11:00-12:00pm
Location: DIMACS Center, CoRE Bldg, Room 431, Rutgers University, Busch Campus, Piscataway, NJ
Abstract:
The organizational theme in an algorithms course is often in terms of "basic algorithmic paradigms" such as greedy algorithms, dynamic programming, divide and conquer, local search, network flows, and (in more advanced or graduate courses) LP rounding, primal dual, algebraic techniques. We usually discuss such concepts by illustrative examples, but rarely (if ever) try to precisely define these algorithmic paradigms and hence cannot rigorously address the question as to their power and limitations.
Greedy algorithms are one of the conceptually simplest algorithmic classes (perhaps along with local search, the conceptually simplest class) for optimization problems. However, it seems hard to agree upon a precise definition for what constitutes a greedy algorithm. Along with a number of colleagues, I have been studying "priority algorithms" as a precise model for greedy algorithms. I will report on some modest progress in the ``war on simplicity'' and try to argue that the attempt (at algorithmic formalization) is worth the effort.