Thumbnail

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

Paschos, Vangelis; Della Croce, Federico; Escoffier, Bruno (2007), Improved worst-case complexity for the MIN 3-SET COVERING problem, Operations Research Letters, 35, 2, p. 205-210. http://dx.doi.org/10.1016/j.orl.2006.02.004

View/Open
Type
Article accepté pour publication ou publié
Date
2007
Journal name
Operations Research Letters
Volume
35
Number
2
Publisher
Elsevier
Pages
205-210
Publication identifier
Metadata
Show full item record
Author(s)
Paschos, Vangelis
Della Croce, Federico
Escoffier, Bruno
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).
Subjects / Keywords
Exact algorithm; MIN SET COVERING; Worst-case complexity