Help Privacy Policy Disclaimer
  Advanced SearchBrowse




Journal Article

Set Covering with Our Eyes Closed


Miettinen,  Pauli
Databases and Information Systems, MPI for Informatics, Max Planck Society;

External Resource
No external resources are shared
Fulltext (restricted access)
There are currently no full texts shared for your IP range.
Fulltext (public)
There are no public fulltexts stored in PuRe
Supplementary Material (public)
There is no public supplementary material available

Grandoni, F., Gupta, A., Leonardi, S., Miettinen, P., Sankowski, P., & Singh, M. (2013). Set Covering with Our Eyes Closed. SIAM Journal on Computing, 42(3), 808-830. doi:10.1137/100802888.

Cite as: https://hdl.handle.net/11858/00-001M-0000-0015-1C37-0
Given a universe $U$ of $n$ elements and a weighted collection $\mathscr{S}$ of $m$ subsets of $U$, the universal set cover problem is to a priori map each element $u \in U$ to a set $S(u) \in \mathscr{S}$ containing $u$ such that any set $X{\subseteq U}$ is covered by $S(X)=\cup_{u\in 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 $\Omega(\sqrt{n})$ 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(\log mn)$ 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.