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.
Autori: | |
Autori: | Grandoni, F; Gupta, A; Leonardi, S; Miettinen, P; Sankowski, P; Singh, M |
Titolo: | Set covering with our eyes closed |
Nome del convegno: | 49th Annual IEEE Symposium on foundations of computer science, FOCS 2008 |
Luogo del convegno: | Philadelphia, PA |
Anno del convegno: | 2008 |
Rilevanza: | Rilevanza internazionale |
Sezione: | contributo |
Data di pubblicazione: | 2008 |
Digital Object Identifier (DOI): | 10.1109/FOCS.2008.31 |
Settore Scientifico Disciplinare: | Settore ING-INF/05 - Sistemi di Elaborazione delle Informazioni |
Lingua: | English |
Tipologia: | Intervento a convegno |
Citazione: | 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. |
Appare nelle tipologie: | 02 - Intervento a convegno |
File in questo prodotto:
File | Descrizione | Tipologia | Licenza | |
---|---|---|---|---|
GGLMSS08focs.pdf | Articolo principale | N/A | ![]() | Administrator Richiedi una copia |