Approximability and parameterized complexity of multicover by c-intervals

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

Onderzoeksoutput: Bijdrage aan tijdschriftTijdschriftartikelAcademicpeer review

2 Citaten (Scopus)
1 Downloads (Pure)

Samenvatting

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
Originele taal-2Engels
Pagina's (van-tot)744-749
Aantal pagina's6
TijdschriftInformation Processing Letters
Volume115
Nummer van het tijdschrift10
DOI's
StatusGepubliceerd - 2015

Vingerafdruk Duik in de onderzoeksthema's van 'Approximability and parameterized complexity of multicover by c-intervals'. Samen vormen ze een unieke vingerafdruk.

Citeer dit