ManuscriptsAn 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.
