Approximability and parameterized complexity of multicover by c-intervals

• c -Interval Multicover is Set Multicover with each input set being the disjoint union of c intervals (a c-interval). • We show 2-Interval Multicover to be W[1]-hard with respect to the parameter “number of 2-intervals used in the cover”. • We show 2-Interval Multicover to be APX-hard even if only...

Full description

Bibliographic Details
Published in:Information processing letters : devoted to the rapid publication of short contributions to information processing, Vol. 115, No. 10 (2015), p. 744-749
Main Author: van Bevern, René
Other Involved Persons: Chen, Jiehua ; Hüffner, Falk ; Kratsch, Stefan ; Talmon, Nimrod ; Woeginger, Gerhard J.
Format: electronic Article
Language:English
Physical Description:Online-Ressource
DOI:10.1016/j.ipl.2015.03.004
QR Code: Show QR Code