  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.
