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.
of these sets such that the maximum number of elements are covered, i.e. the union of the selected sets has maximal size.
This result essentially matches the approximation ratio achieved by the generic greedy algorithm used for maximization of submodular functions with a cardinality constraint.
[1] The maximum coverage problem can be formulated as the following integer linear program.
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
[2] ln-approximability results show that the greedy algorithm is essentially the best-possible polynomial time approximation algorithm for maximum coverage unless
[3] 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.
The basic version is a special case when all weights are
The greedy algorithm for the weighted maximum coverage at each stage chooses a set that contains the maximum weight of uncovered elements.
This algorithm achieves an approximation ratio of
[1] In the budgeted maximum coverage version, not only does every element
that limits the number of sets in the cover a budget
limits the total cost of the cover that can be chosen.
A greedy algorithm will no longer produce solutions with a performance guarantee.
Namely, the worst case behavior of this algorithm might be very far from the optimal solution.
First, define a modified greedy algorithm, that selects the set
that has the best ratio of weighted uncovered elements to cost.
, find the best cover that does not violate the budget.
as starting points, apply the modified greedy algorithm, maintaining the best cover found so far.
At the end of the process, the approximate best cover will be either
This algorithm achieves an approximation ratio of
[5] In the generalized maximum coverage version every set
has a different weight and cost depending on which set covers it.
First, find a solution using greedy algorithm.
In each iteration of the greedy algorithm the tentative solution is added the set which contains the maximum residual weight of elements divided by the residual cost of these elements along with the residual cost of the set.
This algorithm achieves an approximation ratio of