Combinatorial Optimization Reading Group - Noah Weninger

Friday, October 21, 2022 12:00 pm - 12:00 pm EDT (GMT -04:00)

Title: The Probabilistic Set-Covering Problem

Speaker: Noah Weninger
Affiliation: University of Waterloo
Location: MC 6026 or contact Rian Neogi for Zoom link

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.