[Colloquium] REMINDER: Talk by Allan Borodin Today

[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.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20090306/e05a8589/attachment.htm