Set Covering with Our Eyes Wide Shut
Anupam Gupta, Gregory Kehne, Roie Levin · Society for Industrial and Applied Mathematics eBooks · 2024
In the stochastic set cover problem (Grandoni et al., FOCS ‘08), we are given a collection S of m sets over a universe U of size N, and a distribution D over elements of U. The algorithm draws n elements one-by-one from D and must buy a set to cover each element on arrival; the goal is to minimize the total cost of sets bought during this process. A universal algorithm a priori maps each element u ∈ U to a set S(u) such that if U ⊆ U is formed by drawing n times from distribution D, then the algorithm commits to outputting S(U). Grandoni et al. gave an O(log mN)-competitive universal algorithm for this stochastic set cover problem.