Events Calendar

CS Colloquium

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 NP-hard. Fortunately, many NP-hard 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 NP-hard 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 15-year-old 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 post-doctoral 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