Maximum coverage problem: Difference between revisions

Revision as of 09:33, 2 February 2010

Revision as of 04:47, 13 February 2010

Line 1:

{{orphan|date=February 2010}}

The '''maximum coverage problem''' is a classical question in [[computer science]] and [[complexity theory]].

The '''maximum coverage problem''' is a classical question in [[computer science]] and [[computational complexity theory]].

It is a problem whose widely taught in [[approximation algorithms]].

Line 26 ⟶ 28:

algorithm for maximum coverage.{{Citation needed|date=November 2009}}

== Known extensions ==

The inapproximability results apply to all extension all maximum coverage since they hold maximum coverage as a special case.

== Weighted version ==

In the weighted version every element <math> e_j </math> has a weight <math>w(e_j)</math>. The task is to find a maximum coverage which has maximum weight. The basic version is a special case when all weights are <math>1</math>.

Line 40 ⟶ 42:

The greedy algorithm for the weighted maximum coverage at each stage chooses a set which contains the maximum weight of uncovered elements. This algorithm achieves an approximation ratio of <math>\frac{e}{e-1}</math>.{{Citation needed|date=November 2009}}

== Budgeted maximum coverage ==

In the budgeted maximum coverage version, not only does every element <math> e_j </math> have a weight <math>w(e_j)</math>, but also every set <math>S_i</math> has a cost <math>c(S_i)</math>. Instead of <math>k</math> that limits the number of sets in the cover a budget <math>B</math> is given. This budget <math>B</math> limits the weight of the cover that can be chosen.

Line 49 ⟶ 51:

::<math>x_i \in \{0,1\}</math> (if <math>x_i=1</math> then <math>S_i</math> is selected for the cover).

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. The approximation algorithm is extended by the following way. First, after finding a solution using the greedy algorithm, return the better of the greedy algorithm's solution and the set of largest weight. Call this the algorithm the modified greedy algorithm. Second, starting with all possible families of sets of sizes from one to (at least) three, augment these solutions with the modified greedy algorithm. Third, return the best out of all augmented solutions. This algorithm achieves an approximation ratio of <math>\frac{e}{e-1}</math>. This is the best possible approximation ratio unless <math>NP \subseteq DTIME(n^{O(\log\log n)})</math>.<ref>Khuller, S., Moss, A., and Naor, J. 1999. [http://dx.doi.org/10.1016/S0020-0190(99)00031-9 The budgeted maximum coverage problem]. <i>''Inf. Process. Lett</i>''. 70, 1 (Apr. 1999), 39-45.</ref>

== Generalized maximum coverage ==

In the generalized maximum coverage version every set <math>S_i</math> has a cost <math>c(S_i)</math>,

element <math> e_j </math> has a different weight and cost depending on which set covers it.

Line 68 ⟶ 70:

The algorithm uses the concept of residual cost/weight. The residual cost/weight is measured against a tentative solution and its the difference of the cost/weight from the cost/weight gained by a tentative solution.

The algorithm has several stages. 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. Second, compare the solution gained by the first step to the best solution which uses a small number of sets. Third, return the best out of all examined solutions. This algorithm achieves an approximation ratio of <math>\frac{e}{e-1} + o(1)</math>.<ref>Cohen, R. and Katzir, L. 2008. [http://dx.doi.org/10.1016/j.ipl.2008.03.017 The Generalized Maximum Coverage Problem]. <i>''Inf. Process. Lett</i>''. 108, 1 (Sep. 2008), 15-22.</ref>

== Related problems ==

Line 76 ⟶ 78:

{{Reflist}}

* {{Cite book | last=Vazirani | first=Vijay V. | authorlink=Vijay Vazirani | title=Approximation Algorithms | year=2001 | publisher=Springer-Verlag | isbn=3-540-65367-8 | pages=}}

* [[Uriel Feige]], ''A Threshold of ln <math>n</math> for Approximating Set Cover'', Journal of the ACM (JACM), v.45 n.4, p.&nbsp;634 - 652, July 1998.

== External links ==

[[Category:Set families]]

[[Category:NP-complete problems]]