
CS Colloquium
Tue, Feb 22, 2011 @ 03:30 PM  05:00 PM
Thomas Lord Department of Computer Science
Conferences, Lectures, & Seminars
Speaker: Dr. Mohit Singh, McGill University
Talk Title: Iterative Methods in Combinatorial Optimization
Abstract: Many fundamental combinatorial optimization problems including minimum spanning tree, matchings, flows are polynomial time solvable but most problems that arise in practice turn out to be NPhard. Fortunately, many NPhard problems can be modeled by introducing extra side constraints in some fundamental optimization problem. A natural question to ask is whether we can extend any techniques for solving simple combinatorial optimization problems to NPhard variants. In this talk we will demonstrate iterative methods as such a general technique to prove near optimal results for many optimization problems.
We will focus on degree bounded network design problems where the task is to minimize the cost of the network and also satisfy given degree bounds on nodes. The most studied problem in this class is the Minimum Bounded Degree Spanning Tree problem. We will present a polynomial time algorithm that returns a spanning tree of optimal cost while exceeding the degree bound of any vertex by at most an additive one. This is the best possible result for this problem and settles a 15yearold conjecture of Goemans affirmatively.
We will also discuss extensions to degree constrained versions of more general network design problems and give the first additive approximation algorithms using the iterative method. These results add to a rather small list of combinatorial optimization problems which have an additive approximation algorithm.
Biography: Mohit Singh is an Assistant Professor in the School of Computer Science, McGill University since 2010. Mohit Singh received his Bacherlorâs degree in computer science and engineering from Indian Institute of Technology, Delhi in 2003. He obtained his Ph.D. in the Algorithms, Combinatorics and Optimization program from Carnegie Mellon University in 2008 where his advisor was Prof. R. Ravi. He was then a postdoctoral candidate at Microsoft Research, New England. His main research interests are in approximation algorithms, combinatorial optimization and optimization under uncertainty.
Host: Prof. David Kempe
Location: Seaver Science Library (SSL)  150
Audiences: Everyone Is Invited
Contact: Kanak Agrawal