K-approximation of k-hitting set (original) (raw)

In computer science, k-approximation of k-hitting set is an approximation algorithm for weighted hitting set. The input is a collection S of subsets of some universe T and a mapping W from T to non-negative numbers called the weights of the elements of T. In k-hitting set the size of the sets in S cannot be larger than k. That is, . The problem is now to pick some subset T' of T such that every set in S contains some element of T', and such that the total weight of all elements in T' is as small as possible.