• 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 - No thumbnail

Online maximum k-coverage

Ausiello, Giorgio; Boria, Nicolas; Giannakos, Aristotelis; Lucarelli, Giorgio; Paschos, Vangelis (2012), Online maximum k-coverage, Discrete Applied Mathematics, 160, 13-14, p. 1901-1913. http://dx.doi.org/10.1016/j.dam.2012.04.005

Type
Article accepté pour publication ou publié
External document link
https://hal.archives-ouvertes.fr/hal-00876975
Date
2012
Journal name
Discrete Applied Mathematics
Volume
160
Number
13-14
Publisher
Elsevier
Pages
1901-1913
Publication identifier
http://dx.doi.org/10.1016/j.dam.2012.04.005
Metadata
Show full item record
Author(s)
Ausiello, Giorgio
Boria, Nicolas cc
Giannakos, Aristotelis
Lucarelli, Giorgio cc
Paschos, Vangelis
Abstract (EN)
We study an online model for the maximumView the MathML source-vertex-coverage problem, in which, given a graph G=(V,E) and an integer View the MathML source, we seek a subset A⊆V such that View the MathML source and the number of edges covered by A is maximized. In our model, at each step i, a new vertex vi is released, and we have to decide whether we will keep it or discard it. At any time of the process, only View the MathML source vertices can be kept in memory; if at some point the current solution already contains View the MathML source vertices, any inclusion of a new vertex in the solution must entail the definite deletion of another vertex of the current solution (a vertex not kept when released is definitely deleted). We propose algorithms for several natural classes of graphs (mainly regular and bipartite), improving on an easy View the MathML source-competitive ratio. We next settle a set version of the problem, called the maximumView the MathML source-(set)-coverage problem. For this problem, we present an algorithm that improves upon former results for the same model for small and moderate values of View the MathML source.
Subjects / Keywords
Graphs; Maximum k coverage; Competitive ratio; Negative results

Related items

Showing items related by title and author.

  • Thumbnail
    Online Maximum k-Coverage 
    Paschos, Vangelis; Lucarelli, Giorgio; Giannakos, Aristotelis; Boria, Nicolas; Ausiello, Giorgio (2011) Communication / Conférence
  • 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
    On-line models for set-covering: the power of greediness 
    Ausiello, Giorgio; Giannakos, Aristotelis; Paschos, Vangelis (2006) Document de travail / Working paper
  • Thumbnail
    Online models for set-covering: the flaw of greediness 
    Paschos, Vangelis; Giannakos, Aristotelis; Ausiello, Giorgio (2008) Chapitre d'ouvrage
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