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.
As far as we know, the best polynomial-time approximation algorithm for MaxVertexCover is due to Ageev and Sviridenko @cite_11 , and achieves approximation ratio of @math . However, in various settings, it is possible to achieve better results; we mention the papers of @cite_18 and of Galluccio and Nobili @cite_2 as examples.
@cite_18 @cite_2 @cite_11
2004973717 2073925702 1512148653
Abstract We consider the max-vertex-cover (MVC) problem, i.e., find k vertices from an undirected and edge-weighted graph G =( V , E ), where | V |= n ⩾ k , such that the total edge weight covered by the k vertices is maximized. There is a 3 4-approximation algorithm for MVC, based on a linear programming relaxation. We show that the guaranteed ratio can be improved by a simple greedy algorithm for k >(3 4) n , and a simple randomized algorithm for k >(1 2) n . Furthermore, we study a semidefinite programming (SDP) relaxation based approximation algorithms for MVC. We show that, for a range of k , our SDP-based algorithm achieves the best performance guarantee among the four types of algorithms mentioned in this paper. We provide a new LP relaxation of the maximum vertex cover problem and a polynomial-time algorithm that finds a solution within the approximation factor 1-1 (2q@?), where q@? is the size of the smallest clique in a given clique-partition of the edge weighting of G. In this paper we demonstrate a general method of designing constant-factor approximation algorithms for some discrete optimization problems with cardinality constraints. The core of the method is a simple deterministic ("pipage") procedure of rounding of linear relaxations. By using the method we design a (1-(1-1 k)k)-approximation algorithm for the maximum coverage problem where k is the maximum size of the subsets that are covered, and a 1 2-approximation algorithm for the maximum cut problem with given sizes of parts in the vertex set bipartition. The performance guarantee of the former improves on that of the well-known (1 - e-1)-greedy algorithm due to Cornuejols, Fisher and Nemhauser in each case of bounded k. The latter is, to the best of our knowledge, the first constant-factor algorithm for that version of the maximum cut problem.