  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 \rho. 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-\rho)-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.
