Name: R. Ravi
University: Tepper School of Business, Carnegie Mellon University
Date: Friday, May 11, 2007
Time: 1:30 to 3:00 pm
Location: Cooper Auditorium
Title: Iterative Relaxations
Abstract:
Inspired by Kamal Jain’s iterative rounding method for designing approximation algorithms, Singh and Lau have recently designed a variant that has been instrumental in designing the best-possible approximation algorithm for degree bounded minimum-cost spanning trees in undirected graphs. In this talk, I will illustrate its application to the directed counterpart of the problem, by providing an alternate proof of Edmond’s theorem characterizing the directed spanning tree polyhedron, and adapting it to give a bicriteria approximation algorithm. This work is in collaboration with Singh, based on ideas from his work with Lau.
The talk will serve as a preview to a new course to be taught in the Fall 07 (47-853 Special Topics in Combinatorial Optimization, Mondays and Wednesdays 3.30-5.30 Room 318 GSIA, during Mini 1: August 27 - October 15, 2007) by Singh and myself. In this class, we will attempt to re-derive alternate proofs of well known linear characterizations of various famous integral polyhedra using this iterative relaxation technique, which can be considered a primal rounding method.
