PARAMETERIZED EXACT AND APPROXIMATION ALGORITHMS FOR MAXIMUM <i>k</i>-SET COVER AND RELATED SATISFIABILITY PROBLEMS

作     者：Bonnet, Edouard Paschos, Vangelis Th. Sikora, Florian 

作者机构：Hungarian Acad Sci MTA SZTAKI Inst Comp Sci & Control Budapest Hungary PSL Res Univ Univ Paris Dauphine CNRS LAMSADE Paris France 

出 版 物：《RAIRO-THEORETICAL INFORMATICS AND APPLICATIONS》 (法国自动化、信息与运筹学；理论与应用信息)

年 卷 期：2016年第50卷第3期

页      面：227-240页

核心收录：

学科分类：12[管理学] 1201[管理学-管理科学与工程(可授管理学、工学学位)] 08[工学] 0701[理学-数学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主　　题：Parameterized complexity parameterized approximation max k-set cover 

摘      要：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 subfamilyT subset of 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.