René van Bevern, Jiehua Chen, Falk Hüffner, Stefan Kratsch, Nimrod Talmon, and Gerhard J. Woeginger. Approximability and parameterized complexity of multicover by c-intervals. Information Processing Letters, 115(10):744–749, 2015.

A c-interval is the disjoint union of c intervals over N. The c-Interval Multicover problem is the special case of Set Multicover where all sets available for covering are c-intervals. We strengthen known APX-hardness results for c-Interval Multicover, show W[1]-hardness when parameterized by the solution size, and present fixed-parameter algorithms for alternative parameterizations.

bib | DOI | .pdf ] Back

This file was generated by bibtex2html 1.98.