Approximability and parameterized complexity of multicover by c-intervals

R. Bevern, van, J. Chen, F. Hüffner, S. Kratsch, N. Talmon, G.J. Woeginger

Research output: Contribution to journalArticleAcademicpeer-review

4 Citations (Scopus)
1 Downloads (Pure)


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. Keywords: Algorithms; NP-hard problems; APX-hardness; Fixed-parameter tractability; W[1]-hardness; Set cover
Original languageEnglish
Pages (from-to)744-749
Number of pages6
JournalInformation Processing Letters
Issue number10
Publication statusPublished - 2015


Dive into the research topics of 'Approximability and parameterized complexity of multicover by c-intervals'. Together they form a unique fingerprint.

Cite this