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
TypeArticle accepté pour publication ou publié
Journal nameOperations Research Letters
MetadataShow full item record
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 / KeywordsExact algorithm; MIN SET COVERING; Worst-case complexity
Showing items related by title and author.
Exploiting dominance conditions for computing non trivial worst-case complexity for bounded combinatorial optimization problems Paschos, Vangelis; Della Croce, Federico (2008) Article accepté pour publication ou publié