@Article{Bar98c,
  author  =   "R. Bar-Yehuda",
  title =     "Using Homogeneous Weights for Approximating the Partial Cover Problem",
  journal =      "Accepted to J. Algorithms",
  year =         "2000",
  month =         "Sept",
  abstract =     "
In this paper we consider the following natural generalization of two
fundamental problems: the Set-Cover problem and the Min-Knapsack
problem.  We are given an hypergraph, each vertex has a nonnegative
weight and each edge has a nonnegative length. For a given threshold
$\Demand$, our objective is to find a subset of the vertices with
minimum total cost, such that at least a length of $\Demand$ of the
edges are covered.  This problem is called the {\em partial set cover}
problem. We present an $O(\abs{V}^2+\abs{H})$ time, $\B$-approximation
algorithm for this problem, where $\B \geq 2$ is an upper bound on the
edge cardinality of the hypergraph, and $\abs{H}$ is the size of the
hypergraph (i.e. the sum of all its edges cardinalities).
The special case where $\B = 2$ is obviously 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 {\em 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.
      ",
  }