• xmlui.mirage2.page-structure.header.title
    • français
    • English
  • Help
  • Login
  • Language 
    • Français
    • English
View Item 
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
JavaScript is disabled for your browser. Some features of this site may not work without it.

Browse

BIRDResearch centres & CollectionsBy Issue DateAuthorsTitlesTypeThis CollectionBy Issue DateAuthorsTitlesType

My Account

LoginRegister

Statistics

Most Popular ItemsStatistics by CountryMost Popular Authors
Thumbnail

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
cahierLamsade235.pdf (361.2Kb)
Type
Document de travail / Working paper
Date
2006
Publisher
Université Paris-Dauphine
Series title
Cahier du LAMSADE
Series number
235
Published in
Paris
Pages
17
Metadata
Show full item record
Author(s)
Ausiello, Giorgio
Giannakos, Aristotelis
Paschos, Vangelis
Abstract (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-covering

Related items

Showing items related by title and author.

  • Thumbnail
    Online models for set-covering: the flaw of greediness 
    Paschos, Vangelis; Giannakos, Aristotelis; Ausiello, Giorgio (2008) Chapitre d'ouvrage
  • Thumbnail
    Greedy algorithms for on-line set-covering 
    Bourgeois, Nicolas; Ausiello, Giorgio; Paschos, Vangelis; Giannakos, Aristotelis (2009) Article accepté pour publication ou publié
  • Thumbnail
    Greedy algorithms for on-line set-covering and related problems 
    Ausiello, Giorgio; Giannakos, Aristotelis; Paschos, Vangelis (2006) Communication / Conférence
  • Thumbnail
    Online maximum k-coverage 
    Ausiello, Giorgio; Boria, Nicolas; Giannakos, Aristotelis; Lucarelli, Giorgio; Paschos, Vangelis (2012) Article accepté pour publication ou publié
  • Thumbnail
    Online Maximum k-Coverage 
    Paschos, Vangelis; Lucarelli, Giorgio; Giannakos, Aristotelis; Boria, Nicolas; Ausiello, Giorgio (2011) Communication / Conférence
Dauphine PSL Bibliothèque logo
Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16
Phone: 01 44 05 40 94
Contact
Dauphine PSL logoEQUIS logoCreative Commons logo