• français
    • English
  • English 
    • français
    • English
  • Login
JavaScript is disabled for your browser. Some features of this site may not work without it.
BIRD Home

Browse

This CollectionBy Issue DateAuthorsTitlesSubjectsJournals BIRDResearch centres & CollectionsBy Issue DateAuthorsTitlesSubjectsJournals

My Account

Login

Statistics

View Usage Statistics

Online maximum k-coverage

Thumbnail
Date
2012
Link to item file
https://hal.archives-ouvertes.fr/hal-00876975
Dewey
Principes généraux des mathématiques
Sujet
Graphs; Maximum k coverage; Competitive ratio; Negative results
Journal issue
Discrete Applied Mathematics
Volume
160
Number
13-14
Publication date
2012
Article pages
1901-1913
Publisher
Elsevier
DOI
http://dx.doi.org/10.1016/j.dam.2012.04.005
URI
https://basepub.dauphine.fr/handle/123456789/9759
Collections
  • LAMSADE : Publications
Metadata
Show full item record
Author
Ausiello, Giorgio
Boria, Nicolas
Giannakos, Aristotelis
Lucarelli, Giorgio
Paschos, Vangelis
Type
Article accepté pour publication ou publié
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.

  • Accueil Bibliothèque
  • Site de l'Université Paris-Dauphine
  • Contact
SCD Paris Dauphine - Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16

 Content on this site is licensed under a Creative Commons 2.0 France (CC BY-NC-ND 2.0) license.