Approximability and parameterized complexity of multicover by c-intervals

René Van Bevern, Jiehua Chen, Falk Hüffner, Stefan Kratsch, Nimrod Talmon, Gerhard J. Woeginger

Research output: Contribution to journalArticlepeer-review

2 Citations (Scopus)

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.

Original languageEnglish
Pages (from-to)744-749
Number of pages6
JournalInformation Processing Letters
Volume115
Issue number10
DOIs
Publication statusPublished - 1 Oct 2015
Externally publishedYes

Keywords

  • Algorithms
  • APX-hardness
  • Fixed-parameter tractability
  • NP-hard problems
  • Set cover
  • W[1]-hardness

Fingerprint

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

Cite this