Combinatorial Optimization Reading Group - Noah Weninger

Title: The Probabilistic Set-Covering Problem

Abstract: In the classical set-covering problem, we have a set of items and a set S of subsets of the items. The objective is to find a min-cost subset C of S which covers every item, i.e., where every item is contained in at least one of the subsets in C. The probabilistic set-covering problem (PSC) generalizes this to a stochastic setting where the objective is to find a min-cost covering which covers a random subset of the items with probability at least p. We will discuss some structural properties of this problem which lead to a branch-and-bound algorithm for solving it.