Maximum coverage problem

The maximum coverage problem is a classical question in computer science, computational complexity theory, and operations research. It is a problem that is widely taught in approximation algorithms.

As input you are given several sets and a number ${\displaystyle k}$. The sets may have some elements in common. You must select at most ${\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 ${\displaystyle k}$ and a collection of sets ${\displaystyle S=\{S_{1},S_{2},\ldots ,S_{m}\}}$.

Objective: Find a subset ${\displaystyle S'\subseteq S}$ of sets, such that ${\displaystyle \left|S'\right|\leq k}$ and the number of covered elements ${\displaystyle \left|\bigcup _{S_{i}\in S'}{S_{i}}\right|}$ is maximized.

The maximum coverage problem is NP-hard, and can be approximated within ${\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 maximization of submodular functions with a cardinality constraint.^[1]

ILP formulation

The maximum coverage problem can be formulated as the following integer linear program.

Greedy algorithm

The greedy algorithm for maximum coverage chooses sets according to one rule: at each stage, choose a set which contains the largest number of uncovered elements. It can be shown that this algorithm achieves an approximation ratio of ${\displaystyle 1-{\frac {1}{e}}}$.^[2] ln-approximability results show that the greedy algorithm is essentially the best-possible polynomial time approximation algorithm for maximum coverage unless ${\displaystyle P=NP}$.^[3]

Known extensions

The inapproximability results apply to all extensions of the maximum coverage problem since they hold the maximum coverage problem as a special case.

The Maximum Coverage Problem can be applied to road traffic situations; one such example is selecting which bus routes in a public transportation network should be installed with pothole detectors to maximise coverage, when only a limited number of sensors is available. This problem is a known extension of the Maximum Coverage Problem and was first explored in literature by Junade Ali and Vladimir Dyo.^[4]

Weighted version

In the weighted version every element ${\displaystyle e_{j}}$ has a weight ${\displaystyle w(e_{j})}$. The task is to find a maximum coverage which has maximum weight. The basic version is a special case when all weights are ${\displaystyle 1}$.

maximize ${\displaystyle \sum _{e\in E}w(e_{j})\cdot y_{j}}$. (maximizing the weighted sum of covered elements).

subject to ${\displaystyle \sum {x_{i}}\leq k}$; (no more than ${\displaystyle k}$ sets are selected).

${\displaystyle \sum _{e_{j}\in S_{i}}x_{i}\geq y_{j}}$; (if ${\displaystyle y_{j}>0}$ then at least one set ${\displaystyle e_{j}\in S_{i}}$ is selected).

${\displaystyle y_{j}\in \{0,1\}}$; (if ${\displaystyle y_{j}=1}$ then ${\displaystyle e_{j}}$ is covered)

${\displaystyle x_{i}\in \{0,1\}}$ (if ${\displaystyle x_{i}=1}$ then ${\displaystyle S_{i}}$ is selected for the cover).

The greedy algorithm for the weighted maximum coverage at each stage chooses a set that contains the maximum weight of uncovered eleme