I
am currently a fifth year PhD student in ACO (Algorithms,
Combinatorics and Optimization) at Tepper
School of Business and expect to graduate in July 2008. My advisor
is R. Ravi. My
research
focuses on designing efficient algorithms for stochastic and robust
optimization problems and proving a worst-case guarantee (approximation
factor) on their performance. I am also interested in combinatorial
optimization.
We consider the problem of locating k
facilities to service demand that is uncertain and is specified as a
list of scenarios, each scenario being a subset of clients that require
service. The objective is to locate k facilities such that the worst
case connection cost over all scenarios is minimized. We give an O(log
n)-approximation for this problem and generalize the result for several
other location problems. This is joint work with Barbara Anthony, Anupam Gupta, and Viswanath Nagarjan.
We consider the probabilistic set
covering problem where the right hand side is a random 0-1 vector with
a known distribution. The goal is to select a minimum cost family of
sets such that the covering constraints are satisfied with at least a
given probability. Such a constraint is called a ``chance constraint".
We formulate the chance constraint as an MIP and give a family of facet
defining cuts to efficiently solve this MIP for large instances of
problems such as set covering, facility location, k-median etc. This is
joint work with Miguel Lejeune and Anureet Saxena.
3. Incorporating Chance Constraints
into Stochastic and Robust
Optimization models (Manuscript in Preparation).
We study the incorporation of chance
constraints into robust and stochastic covering problems to overcome a
shortcoming of both robust and stochastic models, namely that the
solution cost is often boosted up by the presence of highly unlikely
pathological scenarios. A chance constraint requires that any
feasible solution satisfies not all, but a specified fraction of
scenarios and thus, can be used to prune away suh outlier scenarios.
Chance constraints also generalize the framework of partial covering
problems which have been studied in the literature. This is joint work
with R. Ravi.
We introduce a two-stage demand-robust
model for covering problems where the demand is uncertain and is
specified as an explicit list of second stage scenarios. A feasible
solution specifies a first stage solution and a recourse solution for
each second stage scenario if that scenario materializes such that the
first stage and recourse solution for a scenario together satisfy the
demands of that scenario (the costs in the second stage go up by a
specified factor). The robust objective is to minimize the worst case
total cost of the solution. We prove a structural result about the
first stage solution of a general covering problem and give
approximation algorithms for Steiner tree, multi-cut and facility
location problems in the two-stage robust model. This is joint work
with Kedar Dhamdhere,
R. Ravi
and Mohit Singh.
We consider the two-stage robust and stochastic
versions of the min-cut problem in an undirected weighted graph where
we are given a vertex s, and a list of scenarios, each specifying a
terminal that must be separated from s if that scenario materializes in
the second stage (the edge costs in the second stage are inflated by a
given factor). The goal is to find a two-stage solution that minimizes
the worst case cost for the robust objective and expected cost for the
stochastic objective. We give a 2-approximation for the robust version
and 4-approximation for the stochastic version via a novel charging
argument using Gomory-Hu trees.
This is joint work with Daniel
Golovin and R. Ravi.
We study the problem of finding cost-shares for a
network design problem where a set of customers (each customer is a
subset of locations in a metric) require a network connecting its
locations to a root r. The network can be built using a combination of
backbone edges (high capacity cables that can route any number of
customers) and access edges (low capacity cables that route only a
single customer’s traffic). We give a group-strategyproof pricing
mechanism that is 2-competitive and O(1)-budget-balanced. We show that
the network design problem is related to the two-stage stochastic
Steiner tree problem and obtain a primal-dual constant approximation
for the latter. This is joint work with Anupam Gupta, Stefano Leonardi and R. Ravi.
8. Balanced Facility Location.
GSIA Tech Report 2004.
Joint work with R. Ravi.
9. A 5/4-approximation for the 2-edge
connected subgraph problem on
hamiltonian graphs. Tech Report, June 2003. IIT Delhi.
Joint work with Naveen
Garg, Akash M
Kushal
and Mohit Singh.
