Amitabh Sinha

SODA Conference 2005 Conference Paper

On the approximability of some network design problems

• Julia Chuzhoy
• Anupam Gupta 0001
• Joseph Naor
• Amitabh Sinha

FOCS Conference 2004 Conference Paper

An Edge in Time Saves Nine: LP Rounding Approximation Algorithms for Stochastic Network Design

• Anupam Gupta 0001
• R. Ravi 0001
• Amitabh Sinha

Real-world networks often need to be designed under uncertainty, with only partial information and predictions of demand available at the outset of the design process. The field of stochastic optimization deals with such problems where the forecasts are specified in terms of probability distributions of future data. In this paper, we broaden the set of models as well as the techniques being considered for approximating stochastic optimization problems. For example, we look at stochastic models where the cost of the elements is correlated to the set of realized demands, and risk-averse models where upper bounds are placed on the amount spent in each of the stages. These generalized models require new techniques, and our solutions are based on a novel combination of the primal-dual method truncated based on optimal LP relaxation values, followed by a tree-rounding stage. We use these to give constant-factor approximation algorithms for the stochastic Steiner tree and single sink network design problems in these generalized models.

STOC Conference 2004 Conference Paper

Boosted sampling: approximation algorithms for stochastic optimization

• Anupam Gupta 0001
• Martin Pál
• R. Ravi 0001
• Amitabh Sinha

SODA Conference 2004 Conference Paper

Multicommodity facility location

• R. Ravi 0001
• Amitabh Sinha