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. © 2008 IEEE.

Grandoni, F., Gupta, A., Leonardi, S., Miettinen, P., Sankowski, P., Singh, M. (2008). Set covering with our eyes closed. In FOCS '08 Proceedings of the 2008 49th Annual IEEE Symposium on Foundations of Computer Science (pp.347-356). Washington : IEEE Computer Society [10.1109/FOCS.2008.31].

Set covering with our eyes closed

GRANDONI, FABRIZIO;
2008-01-01

Abstract

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. © 2008 IEEE.
49th Annual IEEE Symposium on foundations of computer science, FOCS 2008
Philadelphia, PA
2008
Rilevanza internazionale
contributo
2008
Settore ING-INF/05 - SISTEMI DI ELABORAZIONE DELLE INFORMAZIONI
English
Computers; Conformal mapping; Facilities; Fiber optic chemical sensors; Image segmentation; Manganese compounds; Competitive factors; Covering problems; Expected costs; Facility locations; Online algorithms; Optimal costs; Optimal sets; Optimization problems; Set cover problems; Set coverings; Weighted sets; Costs
Intervento a convegno
Grandoni, F., Gupta, A., Leonardi, S., Miettinen, P., Sankowski, P., Singh, M. (2008). Set covering with our eyes closed. In FOCS '08 Proceedings of the 2008 49th Annual IEEE Symposium on Foundations of Computer Science (pp.347-356). Washington : IEEE Computer Society [10.1109/FOCS.2008.31].
Grandoni, F; Gupta, A; Leonardi, S; Miettinen, P; Sankowski, P; Singh, M
File in questo prodotto:
File Dimensione Formato  
GGLMSS08focs.pdf

solo utenti autorizzati

Descrizione: Articolo principale
Licenza: Creative commons
Dimensione 247.45 kB
Formato Adobe PDF
247.45 kB Adobe PDF   Visualizza/Apri   Richiedi una copia

Questo articolo è pubblicato sotto una Licenza Licenza Creative Commons Creative Commons

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/2108/31159
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus ND
  • ???jsp.display-item.citation.isi??? ND
social impact