We study approximation algorithms for several variants of the MaxCover problem, with the focus on algorithms that run in FPT time. In the MaxCover problem we are given a set N of elements, a family S of subsets of N, and an integer K. The goal is to find up to K sets from S that jointly cover (i.e., include) as many elements as possible. This problem is well-known to be NP-hard and, under standard complexitytheoretic assumptions, the best possible polynomial-time approximation algorithm has approximation ratio (1 − 1 ). We first consider a variant of MaxCover with bounded element frequencies, i.e., a variant where there is a constant p such that each element belongs to at most p sets in S. For this case we show that there is an FPT approximation scheme (i.e., for each β there is a β-approximation algorithm running in FPT time) for the problem of maximizing the number of covered elements, and a randomized FPT approximation scheme for the problem of minimizing the number of elements left uncovered (we take K to be the parameter). Then, for the case where there is a constant p such that each element belongs to at least p sets from S, we show that the standard greedy approximation algorithm achieves approximation ratio exactly 1 − e −max(pK kSk,1) . We conclude by considering an unrestricted variant of MaxCover, and show approximation algorithms that run in exponential time and combine an exact algorithm with a greedy approximation. Some of our results improve currently known results for MaxVertexCover.
From the point of view of parametrized complexity, MaxVertexCover was first considered by @cite_10 , who have shown that it is @math -complete. The problem was also studied by Cai @cite_13 who gave the currently best exact algorithm for it and by Marx, who gave an FPT approximation scheme @cite_20 . There is also an FPT algorithm for MaxCover , for parameter @math , i.e., the number of elements to cover, due to Bl "a ser @cite_12 .
@cite_13 @cite_10 @cite_12 @cite_20
1994262057 2156896570 2073689249 1980809300
We study the parameterized complexity of cardinality constrained optimization problems, i.e. optimization problems that require their solutions to contain specified numbers of elements to optimize solution values. For this purpose, we consider around 20 such optimization problems, as well as their parametric duals, that deal with various fundamental relations among vertices and edges in graphs. We have almost completely settled their parameterized complexity by giving either FPT algorithms or W[1]-hardness proofs. Furthermore, we obtain faster exact algorithms for several cardinality constrained optimization problems by transforming them into problems of finding maximum (minimum) weight triangles in weighted graphs. Important variants of theVERTEX COVER problem (among others, CONNECTED VERTEX COVER, CAPACITATED VERTEX COVER, and MAXIMUM PARTIAL VERTEX COVER) have been intensively studied in terms of polynomial-time approximability. By way of contrast, their parameterized complexity has so far been completely open. We close this gap here by showing that, with the size of the desired vertex cover as the parameter, CONNECTED VERTEX COVER and CAPACITATED VERTEX COVER are both fixed-parameter tractable while MAXIMUM PARTIAL VERTEX COVER is W[1]-complete. This answers two open questions from the literature. The results extend to several closely related problems. Interestingly, although the considered variants of VERTEX COVER behave very similar in terms of constant factor approximability, they display a wide range of different characteristics when investigating their parameterized complexities. We study the generalization of covering problems such as the set cover problem to partial covering problems. Here we only want to cover a given number k of elements rather than all elements. For instance, in the k-partial (weighted) set cover problem, we wish to compute a minimum weight collection of sets that covers at least k elements. As a main result, we show that the k-partial set cover problem and its special cases like the k-partial vertex cover problem are all fixed parameter tractable (with parameter k). As a second example, we consider the minimum weight k-partial t-restricted cycle cover problem. Approximation algorithms and parameterized complexity are usually considered to be two separate ways of dealing with hard algorithmic problems. In this paper, our aim is to investigate how these two fields can be combined to achieve better algorithms than what any of the two theories could offer. We discuss the different ways parameterized complexity can be extended to approximation algorithms, survey results of this type and propose directions for future research.