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 1604332079 2121638441 2008298964
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. Following the well-studied two-stage optimization framework for stochastic optimization [15,8], we study approximation algorithms for robust two-stage optimization problems with an exponential number of scenarios. Prior to this work, [8] introduced approximation algorithms for two-stage robust optimization problems with explicitly given scenarios. In this paper, we assume the set of possible scenarios is given implicitly, for example by an upper bound on the number of active clients. In two-stage robust optimization, we need to pre-purchase some resources in the first stage before the adversary's action. In the second stage, after the adversary chooses the clients that need to be covered, we need to complement our solution by purchasing additional resources at an inflated price. The goal is to minimize the cost in the worst-case scenario. We give a general approach for solving such problems using LP rounding. Our approach uncovers an interesting connection between robust optimization and online competitive algorithms. We use this approach, together with known online algorithms, to develop approximation algorithms for several robust covering problems, such as set cover, vertex cover, and edge cover. We also study a simple buy-at-oncealgorithm that either covers all items in the first stage or does nothing in the first stage and waits to build the complete solution in the second stage. We show that this algorithm gives tight approximation factors for unweighted variants of these covering problems, but performs poorly for general weighted problems. We study the Steiner tree problem and the single-cable single-sink network design problem under a two-stage stochastic model with recourse and finitely many scenarios. In these models, some edges are purchased in a first stage when only probabilistic information about the second stage is available. In the second stage, one of a finite number of specified scenarios is realized, which results in the set of terminals becoming known and the opportunity to purchase additional edges (under an inflated cost function) to augment the first-stage solution. We provide constant factor approximation algorithms for these problems by rounding the linear relaxation of IP formulations of the problems. Our algorithms involve solving the linear relaxation first, followed by a primal-dual routine that is guided by the LP solution. We also show that because our bounds are local (the cost of each component is bounded by its cost in the LP solution), we are able to obtain bounds that guard against a form of downside risk. We consider two- and multistage versions of stochastic combinatorial optimization problems with recourse: in this framework, the instance for the combinatorial optimization problem is drawn from a known probability distribution @math and is only revealed to the algorithm over two (or multiple) stages. At each stage, on receiving some more information about the instance, the algorithm is allowed to build some partial solution. Since the costs of elements increase with each passing stage, there is a natural tension between waiting for later stages, to gain more information about the instance, and purchasing elements in earlier stages, to take advantages of lower costs. We provide approximation algorithms for stochastic combinatorial optimization problems (such as the Steiner tree problem, the Steiner network problem, and the vertex cover problem) by means of a simple sampling-based algorithm. In every stage, our algorithm samples the probability distribution of the requirements and constructs a partial solution to serve the resulting sample. We show that if one can construct cost-sharing functions associated with the algorithms used to construct these partial solutions, then this strategy results in provable approximation guarantees for the overall stochastic optimization problem. We also extend this approach to provide an approximation algorithm for the stochastic version of the uncapacitated facility location problem, a problem that does not fit into the simpler framework of our main model.