K-Approximation of K-Hitting Set

The k-approximation of k-hitting set is an approximation algorithm for the weighted hitting set problem, in which the goal is to choose a minimum-total-weight collection of elements from a universe so that every set in a given family contains at least one chosen element, under the restriction that no set in the family has more than k elements. The algorithm cannot generally find the optimal solution efficiently, since the underlying problem is computationally hard, but it guarantees a solution whose cost is within a factor of k of the optimum, using a primal-dual method that raises prices on the sets until every set is satisfied by an element that has become fully tight under those prices.