Set Covering with Our Eyes Closed

Grandoni, Fabrizio and Gupta, Anupam and Leonardi, Stefano and Miettinen, Pauli and Sankowski, Piotr and Singh, Mohit (2013) Set Covering with Our Eyes Closed. In: Foundations of Computer Science FOCS '08. IEEE 49th Annual IEEE Symposium, 25.10.2008-28.10.2008, Philadelphia, PA.

Full text not available from this repository.


Given a universe U of n elements and a weighted collection l of m subsets of U, the universal set cover problem is to a-priori map each element u epsi U to a set S(u) epsi l containing u, so that X sube U is covered by S(X)=UuepsiXS(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 Omega(radicn) 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.

Actions (login required)

View Item View Item