[Colloquium] Talk by Allan Borodin, University of Toronto on March 6, 2009

[Katie Casey]

DEPARTMENT OF COMPUTER SCIENCE

UNIVERSITY OF CHICAGO

Date: Friday, March 6, 2009
Time: 2:30 p.m.
Place: RY 251

----------------------------------------------------------

Speaker:	Allan Borodin

From:		University of Toronto

Website: 	http://www.cs.toronto.edu/%7Ebor/

Title:   Sequential Elimination Graphs and Simple Combinatorial  
Algorithms

Abstract:   The local ratio framework introduces by Bar Yehuda and  
Evan in 1981 provides a unified framework for many approximation  
algorithms. Recently, the local ratio technique has been used to  
proved efficient approximation algorithms for a number of packing  
problems. Motivated by these recent algorithms, Akcoglu, Aspnes,  
DasGupta, and Kao suggested a new class of graphs extending the class  
of chordal graphs. Namely, “sequential k-independent graphs”  
generalize the concept of a perfect elimination ordering by allowing  
the “local neighborhood” of each vertex in the ordering to have  
independence number k. We studey this class of graphs and show how  
various graph problems can be efficiently approximated by conceptually  
simple combinatorial algorithms. We also compare this new graph class  
to other known classes of graphs. For example, planar graphs are  
sequentially 3-independent. Sequential k-independent graphs are  
another example of the more general concept of sequential elimination  
graphs. The results in this talk are based on work by Yuli Ye.


Refreshments will be served after the talk in RY 255.