## Approximation Algorithms for Robust Covering Problems with Chance Constraints

journal contribution

posted on 01.11.2003 by Vineet Goyal, Ramamoorthi Ravi#### journal contribution

Any type of content formally published in an academic journal, usually following a peer-review process.

Two common approaches to model uncertainty in optimization problems are to either explicitly enumerate
all the realizations of the uncertain parameters or to specify them implicitly by a probability
distribution over the uncertain parameters. We study robust covering problems where the demand or
the right hand side of the covering constraints is uncertain, in both models of uncertainty and introduce
chance constraints in the formulation. We consider problems with only one stage of decision making as
well as a two-stage problem where there is a second recourse stage to augment the first stage decisions.
In a chance-constrained model, we are given a reliability parameter ℘ (in addition to the other inputs
as in the robust problem) and the goal is to construct a solution that satisfies at least a ℘ fraction of the
scenarios; the robust objective implies that the worst case cost over these scenarios is to be minimized.
Here the parameter ℘ achieves a trade-off between the reliability and the cost of the solution; when
℘ = 1, we arrive back at the classical robust model. This model can thus be thought of as a method for
automatic detection of outlier scenarios. As an example, given ℘ = k/n in an n-node graph, the one-stage
chance constrained shortest path problem from a root with every node as a singleton scenario occurring
with probability 1/n is to find a rooted k-MST.
While it is easy to obtain bi-criteria approximation algorithms for the chance-constrained problems
that violate the chance-constraint by a small factor, we consider the problem of satisfying the chance constraint
strictly. We show that in the explicit scenario model (with more than one element in all
the scenarios), both one-stage and two-stage problems are at least as hard to approximate as the dense
k-subgraph (DkS) problem. The hardness arises particularly due to the requirement that the chance constraint
be satisfied strictly and does not hold if we relax that condition. For the special case when
each scenario has a single element, while the one-stage problem directly reduces to a weighted partial
covering problem, we show that many two-stage problems (including set cover, facility location etc)
reduce to a weighted partial covering problem via a guess and prune method. We consider the two-stage
shortest path problem which can not be reduced to a partial covering version and is closely related to the
weighted k-MST problem where the weight function is submodular. We give an O(log k)-approximation
for this problem using a charging argument.
We also consider the model of uncertainty where scenarios (possibly an exponential number) are
specified implicitly by a probability distribution. In particular, we consider an independent distribution
where each demand occurs with a given probability independently of others. While it is not even clear
if we can succinctly specify the ℘ fraction of selected scenarios for the two-stage problem, we show that
the one-stage problem in this model can be reduced to a weighted partial covering problem. We also
extend these results to obtain a logarithmic approximation for the one-stage problem when the demand
uncertainty is specified by a general probability distribution such that the cumulative probability of any
demand-scenario can be computed efficiently and is strictly-monotone with respect to set inclusion.