Given a universe U of n elements and a weighted collection S of m subsets of U, the universal set cover problem is to a priori map each element u is an element of U to a set S(u) is an element of S containing u such that any set X subset of U is covered by S(X) - boolean OR S-u is an element of X(u). The aim is to find 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 O(root 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 (nonmetric) 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 multicut and disc-covering problems and show how all these universal mappings give us algorithms for the stochastic online variants of the problems with the same competitive factors.

SET COVERING WITH OUR EYES CLOSED / Fabrizio, Grandoni; Anupam, Gupta; Leonardi, Stefano; Pauli, Miettinen; Sankowski, Piotr; Mohit, Singh. - In: SIAM JOURNAL ON COMPUTING. - ISSN 0097-5397. - 42:3(2013), pp. 808-830. [10.1137/100802888]

SET COVERING WITH OUR EYES CLOSED

LEONARDI, Stefano;SANKOWSKI, PIOTR;
2013

Abstract

Given a universe U of n elements and a weighted collection S of m subsets of U, the universal set cover problem is to a priori map each element u is an element of U to a set S(u) is an element of S containing u such that any set X subset of U is covered by S(X) - boolean OR S-u is an element of X(u). The aim is to find 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 O(root 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 (nonmetric) 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 multicut and disc-covering problems and show how all these universal mappings give us algorithms for the stochastic online variants of the problems with the same competitive factors.
2013
facility location; universal algorithms; approximation algorithms; set cover; online algorithms
01 Pubblicazione su rivista::01a Articolo in rivista
SET COVERING WITH OUR EYES CLOSED / Fabrizio, Grandoni; Anupam, Gupta; Leonardi, Stefano; Pauli, Miettinen; Sankowski, Piotr; Mohit, Singh. - In: SIAM JOURNAL ON COMPUTING. - ISSN 0097-5397. - 42:3(2013), pp. 808-830. [10.1137/100802888]
File allegati a questo prodotto
File Dimensione Formato  
VE_2013_11573-559025.pdf

solo gestori archivio

Tipologia: Versione editoriale (versione pubblicata con il layout dell'editore)
Licenza: Tutti i diritti riservati (All rights reserved)
Dimensione 290.66 kB
Formato Adobe PDF
290.66 kB Adobe PDF   Contatta l'autore

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11573/559025
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 15
  • ???jsp.display-item.citation.isi??? 8
social impact