Algorithm

Engineering

Discrete mathematics

Economics

Set (abstract data type)

Data mining

Computer science

Cardinality (data modeling)

Greedy algorithm

Mechanical engineering

Mathematics

Set cover problem

Approximation algorithm

Combinatorics

Programming language

Finance

Cover (algebra)

Order (exchange)

Journal of the ACM

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 .

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

A threshold of ln n for approximating set cover