Approximability and parameterized complexity of multicover by c-intervals

René Van Bevern; Jiehua Chen; Falk Hüffner; Stefan Kratsch; Nimrod Talmon; Gerhard J. Woeginger

doi:10.1016/j.ipl.2015.03.004

Approximability and parameterized complexity of multicover by c-intervals

René Van Bevern, Jiehua Chen, Falk Hüffner, Stefan Kratsch, Nimrod Talmon, Gerhard J. Woeginger

Результат исследования: Научные публикации в периодических изданиях › статья › рецензирование

2 Цитирования (Scopus)

Аннотация

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.

Язык оригинала	английский
Страницы (с-по)	744-749
Число страниц	6
Журнал	Information Processing Letters
Том	115
Номер выпуска	10
DOI	https://doi.org/10.1016/j.ipl.2015.03.004
Состояние	Опубликовано - 1 окт. 2015
Опубликовано для внешнего пользования	Да

Доступ к документу

10.1016/j.ipl.2015.03.004

Другие файлы и ссылки

Link to publication in Scopus

Цитировать

@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",

}

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

В: Information Processing Letters, Том 115, № 10, 01.10.2015, стр. 744-749.

Результат исследования: Научные публикации в периодических изданиях › статья › рецензирование

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 -

Approximability and parameterized complexity of multicover by c-intervals

Аннотация

Доступ к документу

Другие файлы и ссылки

Fingerprint

Цитировать