Approximability and parameterized complexity of multicover by c-intervals

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

doi:10.1016/j.ipl.2015.03.004

Approximability and parameterized complexity of multicover by c-intervals

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

Discrete Mathematics

Research output: Contribution to journal › Article › Academic › peer-review

4 Citations (Scopus)

3 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 language	English
Pages (from-to)	744-749
Number of pages	6
Journal	Information Processing Letters
Volume	115
Issue number	10
DOIs	https://doi.org/10.1016/j.ipl.2015.03.004
Publication status	Published - 2015

Access to Document

10.1016/j.ipl.2015.03.004

Cite this

@article{7446ab2f14e349698277438310e4f62d,

title = "Approximability and parameterized complexity of multicover by c-intervals",

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",

author = "{Bevern, van}, R. and J. Chen and F. H{\"u}ffner and S. Kratsch and N. Talmon and G.J. Woeginger",

year = "2015",

doi = "10.1016/j.ipl.2015.03.004",

language = "English",

volume = "115",

pages = "744--749",

journal = "Information Processing Letters",

issn = "0020-0190",

publisher = "Elsevier B.V.",

number = "10",

}

TY - JOUR

T1 - Approximability and parameterized complexity of multicover by c-intervals

AU - Bevern, van, R.

AU - Chen, J.

AU - Hüffner, F.

AU - Kratsch, S.

AU - Talmon, N.

AU - Woeginger, G.J.

PY - 2015

Y1 - 2015

N2 - 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

AB - 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

U2 - 10.1016/j.ipl.2015.03.004

DO - 10.1016/j.ipl.2015.03.004

M3 - Article

SN - 0020-0190

VL - 115

SP - 744

EP - 749

JO - Information Processing Letters

JF - Information Processing Letters

IS - 10

ER -

Approximability and parameterized complexity of multicover by c-intervals

Abstract

Access to Document

Fingerprint

Cite this