My research interests include dynamic optimization and decision making under
uncertainty. I am interested in the design of tractable approaches for dynamic optimization problems under uncertainty and their applications in electricity markets, revenue management and inventory management problems.
Resume
(pdf)
Submitted
and Working Papers
We consider a two-stage mixed integer stochastic optimization problem and show that a static-robust solution is a good approximation to the fully-adaptable two-stage problem under fairly general assumptions on the uncertainty set and the probability distribution. In particular, if the right hand side of the constraints is uncertain and is distributed symmterically in a bounded symmetric set, then the cost of an optimal fixed solution is at most twice the optimal expected cost. If both the objective coefficients and the right hand sides are uncertain, then the optimal static solution performs arbitrarily worse as compared to the optimal stochastic solution. However, we show that the static solution is a good approximation for the adaptive problem where the objective is to minimize the worst-case cost instead of expected. This is joint work with
D. Bertsimas
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 a stochastic knapsack problem where each item has a known profit but
a random size that is normally distributed independent of other items. The goal
is to select a profit maximizing set of items such that
the probability of the total size exceeding the knapsack bound
is at most a given threshold. We present a PTAS for the problem
via a parametric LP reformulation that efficiently
computes a solution satisfying the
chance-constraint strictly and achieving near-optimal profit. This is
joint with R. Ravi
We consider the problem of minimizing the
product of two non-negative linear cost functions over a polytope and
present a fully polynomial time approximation scheme (FPTAS) for the problem by
reformulating it as a parametrized LP. Our algorithm finds an extreme point
solution and thus, our results directly apply to combinatorial 0-1 problems for
which the convex hull of feasible integer solutions is known such as spanning
trees, matching and sub-modular flows. This is joint work with L. Genc-Kaya and
R. Ravi.
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.
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.
12. Balanced Facility Location.
GSIA Tech Report 2004.
Joint work with R. Ravi.
13. 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.
