TY - GEN

T1 - Set covering with our eyes closed

AU - Grandoni, Fabrizio

AU - Gupta, Anupam

AU - Leonardi, Stefano

AU - Miettinen, Pauli

AU - Sankowski, Piotr

AU - Singh, Mohit

PY - 2008

Y1 - 2008

N2 - Given a universe U of n elements and a weighted collection script capital I of m subsets of U, the universal set cover problem is to a-priori map each element u ∈ U to a set S(u) ∈ script capital I containing u, so that X ⊆ U is covered by S(X) = Uu∈XS(u). The aim is finding 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 Ω(√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 (non-metric) 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 multi-cut and disc-covering problems, and show how all these universal mappings give us stochastic online algorithms with the same competitive factors.

AB - Given a universe U of n elements and a weighted collection script capital I of m subsets of U, the universal set cover problem is to a-priori map each element u ∈ U to a set S(u) ∈ script capital I containing u, so that X ⊆ U is covered by S(X) = Uu∈XS(u). The aim is finding 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 Ω(√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 (non-metric) 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 multi-cut and disc-covering problems, and show how all these universal mappings give us stochastic online algorithms with the same competitive factors.

UR - http://www.scopus.com/inward/record.url?scp=57949114342&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=57949114342&partnerID=8YFLogxK

U2 - 10.1109/FOCS.2008.31

DO - 10.1109/FOCS.2008.31

M3 - Conference contribution

AN - SCOPUS:57949114342

SN - 9780769534367

T3 - Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS

SP - 347

EP - 356

BT - Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2008

T2 - 49th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2008

Y2 - 25 October 2008 through 28 October 2008

ER -