I
am currently a postdoctoral associate in the
Operations Research Center at MIT working with Prof. Dimitris Bertsimas. I did my PhD in Algorithms, Combinatorics and Optimization (ACO)
from Tepper
School of Business, CMU where my advisor
was R. Ravi. My
research
interests lie in the field of dynamic optimization and decision making under
uncertainty with applications in Electricity markets and Inventory management.
I am broadly interested in developing a theory of general solution approaches
for dynamic optimization problems and adapting
these to important application areas including energy markets and inventory
management.
More generally, I am interested
in designing efficient algorithms with provable performance
guarantees for hard optimization problems especially those arising from
real-world applications.
4.
On the Power and Limitations of Affine Policies in Two-Stage Adaptive
Optimization Problems.
Submitted to Math Programming.
(joint with D. Bertsimas)
5.
An Adaptive Local Search Algorithm for Solving Mixed Integer Optimization Problems
. Submitted (2009).
(joint with D. Bertsimas)
6.
Electricity Market Clearing Algorithms under Demand and Capacity Uncertainty.
In Preparation.
(joint with D. Bertsimas)
7. An FPTAS for Minimizing a Class of
Quasi-Concave Functions over a Convex Set.
In Preparation.
(joint with R. Ravi)
8.
Approximation Algorithms for Robust Covering Problems with Chance
Constraints.
Tepper WP 2008-E17.
(joint with R. Ravi)
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 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.
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.
