K-approximation of k-hitting set

The algorithm always terminates because in each iteration of the loop the price of some set in S is increased enough to make one more element from T tight. If it cannot increase any price, it exits. It runs in polynomial time because the loop will not make more iterations than the number of elements in the union of all the sets of S. It returns a hitting set, because when the loop exits, all sets in S contain a tight element from T, and the set of these tight elements are returned.

Note that for any hitting set T* and any prices ${\displaystyle p_{1},\ldots ,p_{|S|}}$ where the invariant from the algorithm is true, the total weight of the hitting set is an upper limit to the sum over all members of T* of the sum of the prices of sets containing this element, that is: ${\displaystyle \Sigma _{a\in T^{*}}\Sigma _{j\in S(a)}p_{j}\leq \Sigma _{a\in T^{*}}W(a)}$. This follows from the invariant property. Further, since the price of every set must occur at least once on the left hand side, we get ${\displaystyle \Sigma _{j\in S}p_{j}\leq \Sigma _{a\in T^{*}}W(a)}$. Especially, this property is true for the optimal hitting set.

Further, for the hitting set H returned from the algorithm above, we have ${\displaystyle \Sigma _{a\in H}\Sigma _{j\in S(a)}p_{j}=\Sigma _{a\in H}W(a)}$. Since any price ${\displaystyle p_{j}}$ can appear at most k times in the left-hand side (since subsets of S can contain no more than k element from T) we get ${\displaystyle \Sigma _{a\in H}W(a)\leq k\cdot \Sigma _{j\in S}p_{j}}$ Combined with the previous paragraph we get ${\displaystyle \Sigma _{a\in H}W(a)\leq k\cdot \Sigma _{a\in T^{*}}W(a)}$, where T* is the optimal hitting set. This is exactly the guarantee that it is a k-approximation algorithm.

This algorithm is an instance of the primal-dual method, also called the pricing method. The intuition is that it is dual to a linear programming algorithm. For an explanation see https://algo.inria.fr/seminars/sem00-01/vazirani.html.

• Kleinberg, J.; Tardos, E. (2006). Algorithm Design. Pearson/Addison-Wesley. ISBN 0-321-29535-8..
• S. Even; R. Bar-Yehuda (1981). "A Linear-Time Approximation Algorithm for the Weighted Vertex Cover Problem". J. Algorithms. 2 (2): 198–203. doi:10.1016/0196-6774(81)90020-1.
• Goemans, M. X.; Williamson, D. P. (1997). "The primal-dual method for approximation algorithms and its application to network design problems". In Hochbaum, Dorit S. (ed.). Approximation Algorithms for NP-Hard Problems. PWS Publishing Company. ISBN 0-534-94968-1..