A threshold of in n for approximating set cover

Given a collection F of subsets of S = {1,..., n}, set cover is the problem of selecting as few as possible subsets from F such that their union cover s S, and max k-cover is the problem of selecting k subsets from F such that their union has maximum cardinality. Both these problems are NP-hard. We p rove that (1 - o(1)) In n is a threshold below which set cover cannot be ap proximated efficiently, unless NP has slightly superpolynomial time algorit hms. This closes the gap (up to low-order terms) between the ratio of appro ximation achievable by the greedy algorithm (which is (1 - o(1)) In n), and previous results of Lund and Yannakakis, that showed hardness of approxima tion within a ratio of (log(2) n)/2 similar or equal to 0.72 In n. For max k-cover, we show an approximation threshold of (1 - 1/e) (up to low-order t erms), under the assumption that P not equal NP.