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

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

0.00 Avg rating0 Votes
Article ID: iaor20082039
Country: Netherlands
Volume: 35
Issue: 2
Start Page Number: 205
End Page Number: 210
Publication Date: Mar 2007
Journal: Operations Research Letters
Authors: , ,
Keywords: programming: integer, location
Abstract:

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

Reviews

Required fields are marked *. Your email address will not be published.