Set covering with our eyes closed

Fabrizio Grandoni, Anupam Gupta, Stefano Leonardi, Pauli Miettinen, Piotr Sankowski, Mohit Singh

Research output: Contribution to journalArticlepeer-review


Given a universe U of n elements and a weighted collection ℐ of m subsets of U, the universal set cover problem is to a priori map each element u ε U to a set S(u)ε ℐ containing u such that any set X ⊆ U is covered by S(X) = ∪uεXS(u). The aim is to find a mapping such that the cost of S(X) is as close as possible to the optimal set cover cost for X. (Such problems are also called oblivious or a priori optimization problems.) Unfortunately, for every universal mapping, the cost of S(X) can be ω(√ν) times larger than optimal if the set X is adversarially chosen. In this paper we study the performance on average, when X is a set of randomly chosen elements from the universe: we show how to efficiently find a universal map whose expected cost is O(logmn) times the expected optimal cost. In fact, we give a slightly improved analysis and show that this is the best possible. We generalize these ideas to weighted set cover and show similar guarantees to (nonmetric) facility location, where we have to balance the facility opening cost with the cost of connecting clients to the facilities. We show applications of our results to universal multicut and disc-covering problems and show how all these universal mappings give us algorithms for the stochastic online variants of the problems with the same competitive factors.

Original languageEnglish (US)
Pages (from-to)808-830
Number of pages23
JournalSIAM Journal on Computing
Issue number3
StatePublished - 2013


  • Approximation algorithms
  • Facility location
  • Online algorithms
  • Set cover
  • Universal algorithms

ASJC Scopus subject areas

  • General Computer Science
  • General Mathematics


Dive into the research topics of 'Set covering with our eyes closed'. Together they form a unique fingerprint.

Cite this