Eastern Great Lakes Theory Workshop Talk

Simple Algorithms for Sequential k-Independent Graphs

Allan Borodin, University of Toronto

Saturday, October 3, 1:30-2:30pm

ABSTRACT

The local ratio framework introduced by Bar Yehuda and Evan in 1981 provides a unified framework for many approximation algorithms. Recently, the local ratio technique has been used to provide 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 study this class of graphs and show how various graph problems (weighted max independent set, weighted m-colorable subgraph, vertex coloring, weighted vertex cover) 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 as are translates of any convex two dimensional object. We will also discuss the more general concept of sequential elimination graphs defined by local neighborhood properties (e.g. degree, clique cover number).

The results in this talk are based on a recent ICALP paper with Yuli Ye.

Speaker Bio

Allan Borodin received his BSC from Rutgers University in 1963, and obtained an MSC degree in 1966 from Stevens Institute of Technology while working as a Member of the Technical Staff at Bell Laboratories. He returned full time to graduate school at Cornell in 1966 and received his PhD in 1969. He came to Canada and the University of Toronto in 1969 for a year or two but forgot to leave. He has been on the faculty of the Department of Computer Science at Toronto since 1969 and served as department chair from 1980-1985. He has held visiting positions at Cornell, ETH Zurich, Universite' de Nice, Hebrew University, Weizmann University, Technion, University of Washington and the Institute for Advanced Study. Professor Borodin is a fellow of the Royal Society of Canada and a recipient of the 2008 CRM-Fields-PIMS Prize.

< Schedule < EaGL-II homepage