A threshold of ln <i>n</i> for approximating set cover

TLDR

Set cover selects the fewest subsets covering a universe and max k‑cover selects k subsets maximizing coverage; both problems are NP‑hard. We prove that approximating set cover within (1−o(1)) ln n is impossible unless NP has slightly superpolynomial algorithms, closing the gap with the greedy algorithm, and that max k‑cover has an approximation threshold of (1−1/e) under P≠NP.

Abstract

Given a collection ℱ of subsets of S = {1,…, n }, set cover is the problem of selecting as few as possible subsets from ℱ such that their union covers S, , and max k-cover is the problem of selecting k subsets from ℱ 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 (log 2 n ) / 2 ≃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 .