Maximum coverage problem

The maximum coverage problem is a classical question in <a href="/facts/Computer_science/lN3pEyPz">computer science</a>, <a href="/facts/Computational_complexity_theory/etHuVF3U">computational complexity theory</a>, and <a href="/facts/Operations_research/H5yJkV5n">operations research</a>.
It is a problem that is widely taught in <a href="/facts/Approximation_algorithms/BWlf7M32">approximation algorithms</a>.
As input you are given several sets and a number 
 
 
 
 k
 
 
 {\displaystyle k}
 
. 
The sets may have some elements in common. 
You must select at most 
 
 
 
 k
 
 
 {\displaystyle k}
 
 of these sets such that the maximum number of elements are covered, 
i.e. the union of the selected sets has maximal size.
Formally, (unweighted) Maximum Coverage 

Instance: A number 
 
 
 
 k
 
 
 {\displaystyle k}
 
 and a collection of sets 
 
 
 
 S
 =
 {
 
 S
 
 1
 
 
 ,
 
 S
 
 2
 
 
 ,
 …
 ,
 
 S
 
 m
 
 
 }
 
 
 {\displaystyle S=\{S_{1},S_{2},\ldots ,S_{m}\}}
 
.
Objective: Find a subset 
 
 
 
 
 S
 ′
 
 ⊆
 S
 
 
 {\displaystyle S'\subseteq S}
 
 of sets, such that 
 
 
 
 
 |
 
 S
 ′
 
 |
 
 ≤
 k
 
 
 {\displaystyle \left|S'\right|\leq k}
 
 and the number of covered elements 
 
 
 
 
 |
 
 
 ⋃
 
 
 S
 
 i
 
 
 ∈
 
 S
 ′
 
 
 
 
 
 S
 
 i
 
 
 
 
 |
 
 
 
 {\displaystyle \left|\bigcup _{S_{i}\in S'}{S_{i}}\right|}
 
 is maximized.
The maximum coverage problem is <a href="/facts/NP-hard/mQeNPv4R">NP-hard</a>, and cannot be approximated to within 
 
 
 
 1
 −
 
 
 1
 e
 
 
 +
 o
 (
 1
 )
 ≈
 0.632
 
 
 {\displaystyle 1-{\frac {1}{e}}+o(1)\approx 0.632}
 
 under standard assumptions. 
This result essentially matches the approximation ratio achieved by the generic greedy algorithm used for <a href="/facts/Submodular_set_function/YNnlKb4U">maximization of submodular functions with a cardinality constraint</a>.

Maximum coverage problem open-in-new

Maximum coverage problem