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. This description is adapted from Wikipedia contributors under CC BY-SA 4.0; changes were made. https://creativecommons.org/licenses/by-sa/4.0/