Parameterized exact and approximation algorithms for maximum k-set cover and related satisfiability problems

Bonnet, Édouard; Paschos, Vangelis; Sikora, Florian

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é

Lien vers un document non conservé dans cette base

https://arxiv.org/abs/1309.4718v3

Date

2016

Nom de la revue

RAIRO - Theoretical Informatics and Applications

Volume

Numéro

Pages

227-240

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]

Résumé (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.