## 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.*