• 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

Improved worst-case complexity for the MIN 3-SET COVERING problem

Thumbnail
View/Open
cahierLamsade232.pdf (282.7Kb)
Date
2007
Dewey
Recherche opérationnelle
Sujet
Exact algorithm; MIN SET COVERING; Worst-case complexity
Journal issue
Operations Research Letters
Volume
35
Number
2
Publication date
2007
Article pages
205-210
Publisher
Elsevier
DOI
http://dx.doi.org/10.1016/j.orl.2006.02.004
URI
https://basepub.dauphine.fr/handle/123456789/2121
Collections
  • LAMSADE : Publications
Metadata
Show full item record
Author
Paschos, Vangelis
Della Croce, Federico
Escoffier, Bruno
Type
Article accepté pour publication ou publié
Abstract (EN)
We consider MIN SET COVERING when the subsets are constrained to have maximum cardinality 3. We propose an exact algorithm whose worst-case complexity is bounded above by O*(1.3957m), where m is the number of sets in the instance. This result improves upon the previously known bound of O*(1.4391m).

  • 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.