| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 428497 | Information Processing Letters | 2015 | 6 Pages |
Abstract
•c-Interval Multicover is Set Multicover with each input set being the disjoint union of c intervals (a c-interval).•We show 2-Interval Multicover to be W[1]-hard with respect to the parameter “number of 2-intervals used in the cover”.•We show 2-Interval Multicover to be APX-hard even if only 1-intervals and 2-intervals consisting of 2 elements are input.
A c-interval is the disjoint union of c intervals over NN. 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.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
René van Bevern, Jiehua Chen, Falk Hüffner, Stefan Kratsch, Nimrod Talmon, Gerhard J. Woeginger,