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é

External document link

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

Date

2016

Journal name

RAIRO - Theoretical Informatics and Applications

Volume

Number

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]

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 cover

JEL

C69 - Other