Geodesic
Parameterized exact and approximation algorithms for maximum k-set cover and related satisfiability problems
Bonnet, Édouard1  ; Paschos, Vangelis Th.2  ; Sikora, Florian2 
1 Institute for Computer Science and Control, Hungarian Academy of Sciences (MTA SZTAKI), Budapest, Hungary.
2 Université Paris-Dauphine, PSL Research University, CNRS, LAMSADE, Paris, France.
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 50 (2016) no. 3, pp. 227-240

Voir la notice de l'article provenant de la source Numdam

Given a family of subsets �� over a set of elements X and two integers p and k, max k-set cover consists of finding a subfamily �� ⊆ �� 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.

Reçu le :
Accepté le :
DOI : 10.1051/ita/2016022
Classification : 68Q17, 68W25
Keywords: Parameterized complexity, parameterized approximation, max k-set cover

Bonnet, Édouard 1 ; Paschos, Vangelis Th. 2 ; Sikora, Florian 2

1 Institute for Computer Science and Control, Hungarian Academy of Sciences (MTA SZTAKI), Budapest, Hungary.
2 Université Paris-Dauphine, PSL Research University, CNRS, LAMSADE, Paris, France. 
@article{ITA_2016__50_3_227_0,
     author = {Bonnet, \'Edouard and Paschos, Vangelis Th. and Sikora, Florian},
     title = {Parameterized exact and approximation algorithms for maximum $k$-set cover and related satisfiability problems},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     pages = {227--240},
     publisher = {EDP-Sciences},
     volume = {50},
     number = {3},
     year = {2016},
     doi = {10.1051/ita/2016022},
     mrnumber = {3582639},
     zbl = {1400.68081},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.1051/ita/2016022/}
}
TY  - JOUR
AU  - Bonnet, Édouard
AU  - Paschos, Vangelis Th.
AU  - Sikora, Florian
TI  - Parameterized exact and approximation algorithms for maximum $k$-set cover and related satisfiability problems
JO  - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY  - 2016
SP  - 227
EP  - 240
VL  - 50
IS  - 3
PB  - EDP-Sciences
UR  - http://geodesic.mathdoc.fr/articles/10.1051/ita/2016022/
DO  - 10.1051/ita/2016022
LA  - en
ID  - ITA_2016__50_3_227_0
ER  - 
%0 Journal Article
%A Bonnet, Édouard
%A Paschos, Vangelis Th.
%A Sikora, Florian
%T Parameterized exact and approximation algorithms for maximum $k$-set cover and related satisfiability problems
%J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
%D 2016
%P 227-240
%V 50
%N 3
%I EDP-Sciences
%U http://geodesic.mathdoc.fr/articles/10.1051/ita/2016022/
%R 10.1051/ita/2016022
%G en
%F ITA_2016__50_3_227_0
Bonnet, Édouard; Paschos, Vangelis Th.; Sikora, Florian. Parameterized exact and approximation algorithms for maximum $k$-set cover and related satisfiability problems. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 50 (2016) no. 3, pp. 227-240. doi: 10.1051/ita/2016022

Cité par Sources :