Stochastic Combinatorial Optimization under Probabilistic Constraints Export

@article{citeulike:3184110, abstract = {In this paper, we present approximation algorithms for combinatorial optimization problems under probabilistic constraints. Specifically, we focus on stochastic variants of two important combinatorial optimization problems: the k-center problem and the set cover problem, with uncertainty 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 efficient approximation algorithms for the case when underlying distribution is a product distribution. In contrast to the expected cost model prevalent in stochastic optimization literature, our problem definitions support restrictions on the probability distributions of the total costs, via incorporating constraints that bound the probability with which the incurred costs may exceed a given threshold.}, archivePrefix = {arXiv}, author = {Agrawal, Shipra and Saberi, Amin and Ye, Yinyu}, citeulike-article-id = {3184110}, citeulike-linkout-0 = {http://arxiv.org/abs/0809.0460}, citeulike-linkout-1 = {http://arxiv.org/pdf/0809.0460}, day = {2}, eprint = {0809.0460}, keywords = {approximation, combinatorial, constraint, probability, probability-density, stochastic}, month = {Sep}, posted-at = {2008-09-03 09:58:07}, priority = {2}, title = {Stochastic Combinatorial Optimization under Probabilistic Constraints}, url = {http://arxiv.org/abs/0809.0460}, year = {2008} }

TY - JOUR ID - citeulike:3184110 L3 - citeulike-article-id:3184110 N2 - In this paper, we present approximation algorithms for combinatorial optimization problems under probabilistic constraints. Specifically, we focus on stochastic variants of two important combinatorial optimization problems: the k-center problem and the set cover problem, with uncertainty 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 efficient approximation algorithms for the case when underlying distribution is a product distribution. In contrast to the expected cost model prevalent in stochastic optimization literature, our problem definitions support restrictions on the probability distributions of the total costs, via incorporating constraints that bound the probability with which the incurred costs may exceed a given threshold. TI - Stochastic Combinatorial Optimization under Probabilistic Constraints KW - approximation KW - combinatorial KW - constraint KW - probability KW - probability-density KW - stochastic AU - Agrawal, Shipra AU - Saberi, Amin AU - Ye, Yinyu PY - 2008/Sep/02/ UR - http://arxiv.org/abs/0809.0460 ER -