Approximability and parameterized complexity of multicover by c-intervals

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