Standard

Approximability and parameterized complexity of multicover by c-intervals. / Van Bevern, René; Chen, Jiehua; Hüffner, Falk et al.

In: Information Processing Letters, Vol. 115, No. 10, 01.10.2015, p. 744-749.

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

Harvard

Van Bevern, R, Chen, J, Hüffner, F, Kratsch, S, Talmon, N & Woeginger, GJ 2015, 'Approximability and parameterized complexity of multicover by c-intervals', Information Processing Letters, vol. 115, no. 10, pp. 744-749. https://doi.org/10.1016/j.ipl.2015.03.004

APA

Van Bevern, R., Chen, J., Hüffner, F., Kratsch, S., Talmon, N., & Woeginger, G. J. (2015). Approximability and parameterized complexity of multicover by c-intervals. Information Processing Letters, 115(10), 744-749. https://doi.org/10.1016/j.ipl.2015.03.004

Vancouver

Van Bevern R, Chen J, Hüffner F, Kratsch S, Talmon N, Woeginger GJ. Approximability and parameterized complexity of multicover by c-intervals. Information Processing Letters. 2015 Oct 1;115(10):744-749. doi: 10.1016/j.ipl.2015.03.004

Author

Van Bevern, René ; Chen, Jiehua ; Hüffner, Falk et al. / Approximability and parameterized complexity of multicover by c-intervals. In: Information Processing Letters. 2015 ; Vol. 115, No. 10. pp. 744-749.

BibTeX

@article{8c91da472a3a48e58844f12734300183,
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, APX-hardness, Fixed-parameter tractability, NP-hard problems, Set cover, W[1]-hardness",
author = "{Van Bevern}, Ren{\'e} and Jiehua Chen and Falk H{\"u}ffner and Stefan Kratsch and Nimrod Talmon and Woeginger, {Gerhard J.}",
year = "2015",
month = oct,
day = "1",
doi = "10.1016/j.ipl.2015.03.004",
language = "English",
volume = "115",
pages = "744--749",
journal = "Information Processing Letters",
issn = "0020-0190",
publisher = "Elsevier",
number = "10",

}

RIS

TY - JOUR

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

AU - Van Bevern, René

AU - Chen, Jiehua

AU - Hüffner, Falk

AU - Kratsch, Stefan

AU - Talmon, Nimrod

AU - Woeginger, Gerhard J.

PY - 2015/10/1

Y1 - 2015/10/1

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.

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.

KW - Algorithms

KW - APX-hardness

KW - Fixed-parameter tractability

KW - NP-hard problems

KW - Set cover

KW - W[1]-hardness

UR - http://www.scopus.com/inward/record.url?scp=84971537241&partnerID=8YFLogxK

U2 - 10.1016/j.ipl.2015.03.004

DO - 10.1016/j.ipl.2015.03.004

M3 - Article

AN - SCOPUS:84971537241

VL - 115

SP - 744

EP - 749

JO - Information Processing Letters

JF - Information Processing Letters

SN - 0020-0190

IS - 10

ER -

ID: 22339874