Fall 2009 Seminar Series

DATE: October 29th
LOCATION: E51-325
TIME: 4:15pm
Reception immediately following in the ORC ConferenceRoom, E40-106

SPEAKER:
R. Ravi

TITLE
Iterative Methods in Combinatorial Optimization

ABSTRACT
In this talk, I will describe a simple iterative method for proving a variety of results in combinatorial optimization. It is inspired by Jain's iterative rounding method for designing approximation algorithms for survivable network design problems, and augmented with a relaxation idea in the work of Lau, Naor, Salvatipour and Singh in their work on designing an approximation algorithm for its degree bounded version. Its application was further refined in recent work of Bansal, Khandekar and Nagarajan on degree-bounded directed network design.

 

In this talk, I will describe its application to showing the integrality of Edmond's characterization of the spanning tree polyhedron and then extend the argument to show a simpler proof of the Lau-Singh approximation algorithm for its degree constrained version. I will conclude by showing how Jain's original proof can be much simplified by the new perspective, by unifying its treatment with that for the STSP problem.

 

This talk describes work of all the above authors interpreted in collaboration with Lau, Nagarajan and Singh.