AbstractIn this paper, we present approximation algorithms for combinatorial optimization problemsunder probabilistic constraints. Speciﬁcally, we focus on stochastic variants of two importantcombinatorial optimization problems: the k-center problem and the set cover problem, with un-certainty characterized by a probability distribution over set of points or elements to be covered.We consider these problems under adaptive and non-adaptive settings, and present eﬃcient ap-proximation algorithms for the case when underlying distribution is a product distribution. Incontrast to the expected cost model prevalent in stochastic optimization literature, our problemdeﬁnitions support restrictions on the probability distributions of the total costs, via incorporat-ing constraints that bound the probability with which the incurred costs may exceed a giventhreshold. 1 Introduction A prevalent model to deal with uncertain data in optimization problems is to minimize expectedcost over an input probability distribution. However, the expected cost model does not adequatelycapture the following two aspects of the problem. Firstly, in many applications, constraint violationscannot be modeled by costs or penalties in any reasonable way (e.g., safety relevant restrictionslike levels of a water reservoir). Thus, if the problem constraints involve an uncertain parameter,one would rather insist on bounding the probability that a decision is infeasible. This leads to
A recent unpublished work by Swamy @cite_8 considers two stage risk-averse models for stochastic set cover and related combinatorial optimization problems. In the two stage recourse model, some sets can be chosen in the first stage at a low cost, and then if a scenario is not covered, more sets can be bought in the second stage as a recourse action. The risk averse problem is to minimize the sum of first stage cost and value-at-risk for the second stage. It was observed that if the value-at-risk for second stage is fixed to be @math , the problem reduces to chance-constrained set cover without recourse - same as our non-adaptive set cover problem. Although the algorithms in @cite_8 can be used under more general assumptions of black box distributions", we present faster algorithms that achieve better approximation factors for the special case of product distributions. Specifically, in contrast to the results in @cite_8 , we do not incur any approximation in the probabilistic constraint, and the running time of our algorithms is independent of the input threshold @math .
@cite_8
1578746725
We consider various stochastic models that incorporate the notion of risk-averseness into the standard 2-stage recourse model, and develop novel techniques for solving the algorithmic problems arising in these models. A key notable feature of our work that distinguishes it from work in some other related models, such as the (standard) budget model and the (demand-) robust model, is that we obtain results in the black-box setting, that is, where one is given only sampling access to the underlying distribution. Our first model, which we call the risk-averse budget model, incorporates the notion of risk-averseness via a probabilistic constraint that restricts the probability (according to the underlying distribution) with which the second-stage cost may exceed a given budget B to at most a given input threshold . We also a consider a closely-related model that we call the risk-averse robust model, where we seek to minimize the first-stage cost and the (1- )-quantile of the second-stage cost. We obtain approximation algorithms for a variety of combinatorial optimization problems including the set cover, vertex cover, multicut on trees, min cut, and facility location problems, in the risk-averse budget and robust models with black-box distributions. We obtain near-optimal solutions that preserve the budget approximately and incur a small blow-up of the probability threshold (both of which are unavoidable). To the best of our knowledge, these are the first approximation results for problems involving probabilistic constraints and black-box distributions. A major component of our results is a fully polynomial approximation scheme for solving the LP-relaxation of the risk-averse problem.