
On-line models for set-covering: the power of greediness
Ausiello, Giorgio; Giannakos, Aristotelis; Paschos, Vangelis (2006), On-line models for set-covering: the power of greediness. https://basepub.dauphine.fr/handle/123456789/9728
View/ Open
Type
Document de travail / Working paperDate
2006Publisher
Université Paris-Dauphine
Series title
Cahier du LAMSADESeries number
235Published in
Paris
Pages
17
Metadata
Show full item recordAbstract (EN)
We study an on-line model for set-covering implying that elements of the ground set of size n arrive one-by-one and with any such element i, arrive also the names of the sets containing it in the fi nal instance. Any new element has to be processed irrevocably before the arrival of the next element. We study limits on the competitiveness of several greedy rules solving several alternatives of this basic model. For any of them we give lower and upper bounds for the competitive ratio achieved. We finally deal with the maximum budget saving problem. Here, an initial budget is allotted that is destined to cover the cost of an algorithm for solving set-covering and the objective is to maximize the savings on the initial budget.Subjects / Keywords
set-coveringRelated items
Showing items related by title and author.
-
Paschos, Vangelis; Giannakos, Aristotelis; Ausiello, Giorgio (2008) Chapitre d'ouvrage
-
Bourgeois, Nicolas; Ausiello, Giorgio; Paschos, Vangelis; Giannakos, Aristotelis (2009) Article accepté pour publication ou publié
-
Ausiello, Giorgio; Giannakos, Aristotelis; Paschos, Vangelis (2006) Communication / Conférence
-
Ausiello, Giorgio; Boria, Nicolas; Giannakos, Aristotelis; Lucarelli, Giorgio; Paschos, Vangelis (2012) Article accepté pour publication ou publié
-
Paschos, Vangelis; Lucarelli, Giorgio; Giannakos, Aristotelis; Boria, Nicolas; Ausiello, Giorgio (2011) Communication / Conférence