CINECA IRIS Institutional Research Information System
IRIS è la soluzione IT che facilita la raccolta e la gestione dei dati relativi alle attività e ai prodotti della ricerca. Fornisce a ricercatori, amministratori e valutatori gli strumenti per monitorare i risultati della ricerca, aumentarne la visibilità e allocare in modo efficace le risorse disponibili.
EnglishGiven 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): | http://dx.doi.org/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 |
Copyright © 2020