Parameterized exact and approximation algorithms for maximum k-set cover and related satisfiability problems
Bonnet, Édouard; Paschos, Vangelis; Sikora, Florian (2016), Parameterized exact and approximation algorithms for maximum k-set cover and related satisfiability problems, RAIRO - Theoretical Informatics and Applications, 50, 3, p. 227-240. 10.1051/ita/2016022
Type
Article accepté pour publication ou publiéExternal document link
https://arxiv.org/abs/1309.4718v3Date
2016Journal name
RAIRO - Theoretical Informatics and ApplicationsVolume
50Number
3Pages
227-240
Publication identifier
Metadata
Show full item recordAuthor(s)
Bonnet, Édouard
Institute for Computer Science and Control [Budapest] [SZTAKI]
Paschos, Vangelis
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Sikora, Florian

Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Abstract (EN)
Given a family of subsets S over a set of elements X and two integers p and k, max k-set cover consists of finding a subfamily T ⊆ S of cardinality at most k, covering at least p elements of X. This problem is W[2]-hard when parameterized by k, and FPT when parameterized by p. We investigate the parameterized approximability of the problem with respect to parameters k and p. Then, we show that max sat-k, a satisfiability problem generalizing max k-set cover, is also FPT with respect to parameter p.Subjects / Keywords
Parameterized complexity; parameterized approximation; max k-set coverJEL
C69 - OtherRelated items
Showing items related by title and author.
-
Bonnet, Edouard; Escoffier, Bruno; Paschos, Vangelis; Stamoulis, Georgios (2018) Article accepté pour publication ou publié
-
Bourgeois, Nicolas; Escoffier, Bruno; Paschos, Vangelis (2011) Article accepté pour publication ou publié
-
Bonnet, Edouard; Escoffier, Bruno; Paschos, Vangelis; Stamoulis, Giorgios (2016) Communication / Conférence
-
Bonamy, Marthe; Bonnet, Edouard; Bousquet, Nicolas; Charbit, Pierre; Giannopoulos, Panos; Kim, Eun Jung; Rzążewski, P.; Sikora, Florian; Thomassé, S. (2021) Article accepté pour publication ou publié
-
Bonnet, Édouard; Giannopoulos, Panos; Kim, Eun Jung; Rzążewski, Pawel; Sikora, Florian (2018) Communication / Conférence