Spyros Angelopoulous
University of Toronto
Abstract: Greedy algorithms have been a widely used paradigm for solving combinatorial optimization problems; for many algorithm designers, a greedy algorithm is the first approach to try when facing a specific problem. Even though identyfying an algorithm as greedy is usually relatively simple, such identification relies (most times, if not always) on intuition and experience; for instance, students in an undergraduate class are usually told "you will recognize one when you see one". Unfortunately, intuition is not sufficient if one wants to show that a certain problem cannot be solved efficiently by a greedy algorithm.
In a recent paper (SODA 2002) Borodin, Nielsen and Rackoff proposed a definition that abstracts the main properties of greedy and greedy-like (deterministic) approximation algorithms, by introducing the class of priority algorithms. They did so in the context of classical scheduling problems, but claimed that the definitions could be extended to other problem domains. In this talk, I will describe how the priority-algorithm framework can be applied (and extended) to the facility location and set cover problems. Similar to the competitive analysis of on-line algorithms, we are able to show limitations on the approximation power of priority algorithms based only on the structure of the algorithm, while allowing unbounded time complexity. I will also describe how the priority-algorithm framework can be extended to capture randomized greedy-like algorithms.
Joint work with Allan Borodin.