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 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 NP-hard, 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 maximization of submodular functions with a cardinality constraint.
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 1 − 1 e {\displaystyle 1-{\frac {1}{e}}} . ln-approximability results show that the greedy algorithm is essentially the best-possible polynomial time approximation algorithm for maximum coverage unless P = N P {\displaystyle P=NP} .
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.
Weighted version In the weighted version every element e j {\displaystyle e_{j}} has a weight w ( e j ) {\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 1 {\displaystyle 1} .
maximize ∑ e ∈ E w ( e j ) ⋅ y j {\displaystyle \sum _{e\in E}w(e_{j})\cdot y_{j}} . (maximizing the weighted sum of covered elements). subject to ∑ x i ≤ k {\displaystyle \sum {x_{i}}\leq k} ; (no more than k {\displaystyle k} sets are selected).
∑ e j ∈ S i x i ≥ y j {\displaystyle \sum _{e_{j}\in S_{i}}x_{i}\geq y_{j}} ; (if y j > 0 {\displaystyle y_{j}>0} then at least one set e j ∈ S i {\displaystyle e_{j}\in S_{i}} is selected).
… excerpt ends here. Continue reading the full article.
