Using Homogeneous Weights for Approximating the Partial Cover Problem |
| |
Authors: | Reuven Bar-Yehuda |
| |
Affiliation: | Computer Science Department, Technion–Israel Institute of Technology, Haifa, 32000, Israel |
| |
Abstract: | In this paper we consider the natural generalizations of two fundamental problems, the Set-Cover problem and the Min-Knapsack problem. We are given a hypergraph, each vertex of which has a nonnegative weight, and each edge of which has a nonnegative length. For a given threshold , our objective is to find a subset of the vertices with minimum total cost, such that at least a length of of the edges is covered. This problem is called the partial set cover problem. We present an O(|V|2 + |H|)-time, ΔE-approximation algorithm for this problem, where ΔE ≥ 2 is an upper bound on the edge cardinality of the hypergraph and |H| is the size of the hypergraph (i.e., the sum of all its edges cardinalities). The special case where ΔE = 2 is called the partial vertex cover problem. For this problem a 2-approximation was previously known, however, the time complexity of our solution, i.e., O(|V|2), is a dramatic improvement.We show that if the weights are homogeneous (i.e., proportional to the potential coverage of the sets) then any minimal cover is a good approximation. Now, using the local-ratio technique, it is sufficient to repeatedly subtract a homogeneous weight function from the given weight function. |
| |
Keywords: | approximation algorithm local ratio covering problems vertex cover set cover partial covering knapsack |
本文献已被 ScienceDirect 等数据库收录! |
|