Approximability and parameterized complexity of multicover by c-intervals

0.00 Avg rating—0 Votes

Article ID:	iaor201527219
Volume:	115
Issue:	10
Start Page Number:	744
End Page Number:	749
Publication Date:	Oct 2015
Journal:	Information Processing Letters
Authors:	Woeginger Gerhard J, Hffner Falk, Kratsch Stefan, van Bevern Ren, Chen Jiehua, Talmon Nimrod
Keywords:	approximation, covering problems, interval arithmetic

Abstract:

A c‐interval is the disjoint union of c intervals over $‐ N$ equ1 . 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.

Reviews

Required fields are marked *. Your email address will not be published.