DEPARTMENT SEMINAR

Mohit Singh Carnegie Mellon University Tepper School of Business

Tuesday, April 1, 2008 Computer Science Building, Rooms 151 4:00 PM

Faculty Host: Ramesh Sitaraman

"Iterative Methods in Combinatorial Optimization"

Linear programming has been a successful tool in combinatorial
optimization to achieve polynomial time algorithms for problems in P
and also to achieve good approximation Algorithms for problems which
are NP-hard. We demonstrate that iterative methods give a general
framework to analyze linear programming formulations of polynomial
time solvable problems as well NP-hard problems.

In this talk, we 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. These problems generalize key problems in
combinatorial optimization and also have applications in various areas
including VLSI design, vehicle routing and communication networks. The
most well-studied problem in this class is the Minimum Bounded Degree
Spanning Tree problem. We 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 show first additive approximation
algorithms for these problems Using the iterative method. These
results add to a rather small list of combinatorial optimization
problems which have an additive approximation algorithm and show that
iterative methods provide a unifying framework for solving large class
of constrained network design problems.

BIO:

Mohit Singh is a graduate student with Prof R. Ravi at Carnegie Mellon
University in the Algorithms, Combinatorics and Optimization (ACO)
program. Before joining Carnegie Mellon, he received a Bachelors of
Technology from IIT Delhi. His research interests include designing
new algorithms using mathematical programming techniques for various
optimization problems and analyzing new models which incorporate
uncertainty in data of optimization problems.


Refreshments at 3:40 PM in the atrium, outside the presentation room.