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

2 Citations (Scopus)
1 Downloads (Pure)

Abstract

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
Volume115
Issue number10
DOIs
Publication statusPublished - 2015

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

  • Cite this