Set Covering with Our Eyes Wide Shut

Anupam Gupta, Gregory Kehne, Roie Levin

Research output: Contribution to conferencePaperpeer-review


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. We improve unilaterally upon this result by giving a simple, polynomial time O(log mn)-competitive universal algorithm for the more general prophet version, in which U is formed by drawing from n different distributions D1, ..., Dn. Furthermore, we show that we do not need full foreknowledge of the distributions: in fact, a single sample from each distribution suffices. We show similar results for the 2-stage prophet setting and for the online-with-a-sample setting. We obtain our results via a generic reduction from the single-sample prophet setting to the random-order setting (for which Gupta et al., FOCS 2021 provides an algorithm); this reduction holds for a broad class of minimization problems that includes all covering problems. We take advantage of this framework by giving random-order algorithms for non-metric facility location and set multicover; using our framework, these automatically translate to universal prophet algorithms.

Original languageEnglish (US)
Number of pages24
StatePublished - 2024
Event35th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2024 - Alexandria, United States
Duration: Jan 7 2024Jan 10 2024


Conference35th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2024
Country/TerritoryUnited States

ASJC Scopus subject areas

  • Software
  • General Mathematics


Dive into the research topics of 'Set Covering with Our Eyes Wide Shut'. Together they form a unique fingerprint.

Cite this