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

Thumbnail
Ouvrir
Date
2007
Indexation documentaire
Recherche opérationnelle
Subject
Exact algorithm; MIN SET COVERING; Worst-case complexity
Nom de la revue
Operations Research Letters
Volume
35
Numéro
2
Date de publication
2007
Pages article
205-210
Nom de l'éditeur
Elsevier
DOI
http://dx.doi.org/10.1016/j.orl.2006.02.004
URI
https://basepub.dauphine.fr/handle/123456789/2121
Collections
Métadonnées
Afficher la notice complète
Auteur
Paschos, Vangelis
Della Croce, Federico
Escoffier, Bruno
Type
Article accepté pour publication ou publié
Résumé en anglais
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).