Hardness of approximating set cover

Yuval Filmus

An exposition of Feige’s celebrated result on the hardness of approximating set cover.

This talk was given as part of the PCP reading group on 23/1/2010.


See also an exposition of the hardness of maximum coverage, the dual problem, which uses the modern proof due to Dana Moshkovitz.