×

zbMATH — the first resource for mathematics

Approximability and parameterized complexity of multicover by \(c\)-intervals. (English) Zbl 1329.68149
Summary: A \(c\)-interval is the disjoint union of \(c\) intervals over \(\mathbb 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.

MSC:
68Q25 Analysis of algorithms and problem complexity
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
68W25 Approximation algorithms
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] van Bevern, R.; Mnich, M.; Niedermeier, R.; Weller, M., Interval scheduling and colorful independent sets, J. Sched., (2014)
[2] van Bevern, R.; Downey, R. G.; Fellows, M. R.; Gaspers, S.; Rosamond, F. A., Myhill-nerode methods for hypergraphs, Algorithmica, (2015) · Zbl 1335.68098
[3] Ding, L.; Fu, B.; Zhu, B., Minimum interval cover and its application to genome sequencing, (Proc. 5th COCOA, Lect. Notes Comput. Sci., vol. 6831, (2011), Springer), 287-298 · Zbl 1342.68145
[4] L. Ding, B. Fu, B. Zhu, Minimum paired-end interval cover and its application, Manuscript, May 2012, http://www.cs.montana.edu/bhz/doc/tcbb12-1.pdf.
[5] Dom, M., Algorithmic aspects of the consecutive-ones property, Bull. Eur. Assoc. Theor. Comput. Sci., 98, 27-59, (2009) · Zbl 1179.05071
[6] Downey, R. G.; Fellows, M. R., Fundamentals of parameterized complexity, (2013), Springer · Zbl 1358.68006
[7] Fellows, M. R.; Hermelin, D.; Rosamond, F.; Vialette, S., On the parameterized complexity of multiple-interval graph problems, Theor. Comput. Sci., 410, 1, 53-61, (2009) · Zbl 1161.68038
[8] Flum, J.; Grohe, M., Parameterized complexity theory, (2006), Springer
[9] Halldórsson, M. M.; Karlsson, R. K., Strip graphs: recognition and scheduling, (Proc. 32nd WG, Lect. Notes Comput. Sci., vol. 4271, (2006)), 137-146 · Zbl 1167.68409
[10] Hochbaum, D. S.; Levin, A., Cyclical scheduling and multi-shift scheduling: complexity and approximation algorithms, Discrete Optim., 3, 4, 327-340, (2006) · Zbl 1112.90023
[11] Kann, V., Maximum bounded 3-dimensional matching is MAX SNP-complete, Inf. Process. Lett., 37, 1, 27-35, (1991) · Zbl 0711.68045
[12] Marx, D., Parameterized complexity and approximation algorithms, Comput. J., 51, 1, 60-78, (2008)
[13] Niedermeier, R., Invitation to fixed-parameter algorithms, (2006), Oxford University Press · Zbl 1095.68038
[14] Williamson, D. P.; Shmoys, D. B., The design of approximation algorithms, (2011), Cambridge University Press · Zbl 1219.90004
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.