Mohit Singh Colloquium, 02/22
David Kempe
hot on the heels of Virginia Vassilevska-Williams, we have another
exciting theory speaker. On Tuesday, 02/22, Mohit Singh from McGill
University will be visiting us. All the information on his talk is
below. Looking forward to seeing many of you there.
Date: Tuesday, 02/22, 3:30 PM
Location: SSL 150
Speaker: Mohit Singh, McGill University
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.
Bio:
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.
--
David Kempe <dke...@usc.edu>