A threshold of ln <italic>n</italic> 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 covers 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 prove that (1 - o(1)) ln n is a threshold below which set cover cannot be approximated efficiently, unless NP has slightly superpolynomial time algorithms. This closes the gap (up to low-order terms) between the ratio of approximation achievable by the greedy alogorithm (which is (1 - o(1)) ln n), and provious results of Lund and Yanakakis, that showed hardness of approximation within a ratio of log2 n/2&sime;0.72 ln n. For max k-cover, we show an approximation threshold of (1 - 1/e)(up to low-order terms), under assumption that P≠NP.