Bicriteria Approximation of Chance-Constrained Covering Problems

A chance-constrained optimization problem involves constraints with random data that can be violated with probability bounded from above by a prespecified small risk parameter. Such constraints are used to model reliability requirements in a variety of application areas, such as finance, energy, service, and manufacturing. Except under very special conditions, chance-constrained problems are extremely difficult. There has been a great deal of elegant work on developing tractable approximations of chance constraints. Unfortunately, none of these approaches comes with a constant factor approximation guarantee. We show that such a guarantee is impossible by proving an inapproximability result. By contrast, for a large class of chance-constrained covering problems, we propose a bicriteria approximation scheme. Our scheme finds a solution whose violation probability may be larger than but is within a constant factor of the specified risk parameter and whose objective value is within a constant factor of the true optimal value. Key to our developments is the construction of a tractable convex relaxation of a chance-constrained problem and an appropriate scaling of a solution to this relaxation. We extend our approximation results to the setting in which the underlying distribution of the constraint data is not known. That is, we consider distributionally robust chance-constrained covering problems with convex moment and Wasserstein ambiguity sets and provide bicriteria approximation results.