A threshold of ln n for approximating set cover (preliminary version)
Uriel Feige · 1996
We prove that (] -o(]))lnn is a threshold below which set, cover cannot be approximated efficiently, unless NP has slightly superpolynornial time algorithms.This closes tlw gap (up to low order terms) between the ratio of ap-prox&ation achievable by the greedy algorithm (which is (1 -O( 1 ) ) in n), and previous results of Lund and Yannakakis, that showed harclness of approximation within a ratio of (log2 7/)/2 E 0.7.?111 //,, 1