• 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 the differential approximation of MIN SET COVER

Bazgan, Cristina; Monnot, Jérôme; Paschos, Vangelis; Serrière, Fabrice (2005), On the differential approximation of MIN SET COVER, Theoretical Computer Science, 332, 1-3, p. 497-513. http://dx.doi.org/10.1016/j.tcs.2004.12.022

View/Open
cahier219.pdf (220.1Kb)
Type
Article accepté pour publication ou publié
Date
2005
Journal name
Theoretical Computer Science
Volume
332
Number
1-3
Publisher
Elsevier
Pages
497-513
Publication identifier
http://dx.doi.org/10.1016/j.tcs.2004.12.022
Metadata
Show full item record
Author(s)
Bazgan, Cristina
Monnot, Jérôme cc
Paschos, Vangelis
Serrière, Fabrice
Abstract (EN)
We present in this paper differential approximation results for MIN SET COVER and MIN WEIGHTED SET COVER. We first show that the differential approximation ratio of the natural greedy algorithm for MIN SET COVER is bounded below by 1.365/Δ and above by 4/(Δ+1), where Δ is the maximum set-cardinality in the MIN SET COVER-instance. Next, we study another approximation algorithm for MIN SET COVER that computes 2-optimal solutions, i.e., solutions that cannot be improved by removing two sets belonging to them and adding another set not belonging to them. We prove that the differential approximation ratio of this second algorithm is bounded below by 2/(Δ+1) and that this bound is tight. Finally, we study an approximation algorithm for MIN WEIGHTED SET COVER and provide a tight lower bound of 1/Δ. Our results identically hold for MAX HYPERGRAPH INDEPENDENT SET in both the standard and the differential approximation paradigms.
Subjects / Keywords
Complexity; Approximation algorithms; Greedy algorithm; Set cover; Combinatorial problem

Related items

Showing items related by title and author.

  • Thumbnail
    Greedy differential approximations for MIN SET COVER 
    Bazgan, Cristina; Monnot, Jérôme; Paschos, Vangelis; Serrière, Fabrice (2005) Communication / Conférence
  • Thumbnail
    Differential approximations for min set cover 
    Bazgan, Cristina; Monnot, Jérôme; Paschos, Vangelis; Serrière, F. (2005) Article accepté pour publication ou publié
  • Thumbnail
    The many facets of upper domination 
    Bazgan, Cristina; Brankovic, Ljiljana; Casel, Katrin; Fernau, Henning; Jansen, Klaus; Klein, Kim-Manuel; Lampis, Michael; Liedloff, Mathieu; Monnot, Jérôme; Paschos, Vangelis (2018) Article accepté pour publication ou publié
  • Thumbnail
    Efficient approximation of MIN SET COVER by moderately exponential algorithms 
    Paschos, Vangelis; Escoffier, Bruno; Bourgeois, Nicolas (2009) Article accepté pour publication ou publié
  • Thumbnail
    Approximation of max independent set, min vertex cover and related problems by moderately exponential algorithms 
    Bourgeois, Nicolas; Escoffier, Bruno; Paschos, Vangelis (2011) Article accepté pour publication ou publié
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