<p>This problem is known as MAX-COVER. A good algorithm for MAX-COVER is the greedy algorithm: at each stage, we pick a set which maximizes the number of uncovered elements. This algorithm produces a cover of size $s$ which covers a fraction of $1-1/e$ of the optimum. Feige proved that it is NP-hard to outperform this algorithm by any constant.</p>

CC BY-SA 2.5
2011-01-27T17:50:19.620Z
2011-01-27T17:50:19.620Z
Yuval Filmus
<p>Given a set of $n$ configurations $C_1 , C_2 ... C_n$ and a function $f$ such that $f(C_i)$ produces a set of $m$ results $R_1, R_2 ... R_m$ where $R_j=\{0,1\}$</p>

<p>We only care about the $\Sigma f(C_i)$ - i.e. $Rj = 1$ if any $f(C_i)$ has $R_j = 1$</p>

<p>What is an efficient algorithm to find a subset of $C$ of size $s$ such that a maximum number of $R_j = 1$ are found?</p>

<p>A secondary problem is to have the subset sorted such that new $R_j = 1$ are found first. i.e  $f(C_{i+1})$ will find $\leq$ new $R_j = 1$ than $f(C_i)$</p>

CC BY-SA 2.5
2011-01-27T13:17:56.040Z
What is the relationship between $C$ and the $C_i$? What is the relationship between $R$ and the $R_i$?
Peter Taylor
CC BY-SA 2.5
2011-01-27T13:39:34.187Z
Updated to clarify that $C_i$ and $R_j$ are particular instances of $C$ and $R$
Callum
CC BY-SA 2.5
2011-01-28T01:35:30.023Z
After reading Yuval’s answer, I understand the first question is about the maximum cover problem.  I still have no idea what the second question means.
Tsuyoshi Ito
CC BY-SA 2.5
2011-01-28T04:23:09.737Z
Sorry, but I find this question completely incoherent.  If R_j = {0,1} for all j, then the "set of m results" R_1, R_2, ..., R_m is actually just a set of one result: {{0,1}}.  That can't be right.  So which one is R_j, and what does R_i equal when i≠j?  What does it mean for f(C_i) to  "produce" a set of results, or for f(C_i) to "have" R_j = 1?  (Unlike Tsuyoshi, I can't mentally massage the problem statement into anything resembling maximum cover.)
Jeffε
CC BY-SA 2.5
2011-01-28T09:25:15.003Z
@JeffE: My interpretation of the question (which was only possible after reading Yuval’s answer) is the following.  f is a hypergraph with n hyperedges labeled C_1,…,C_n and m vertices labeled R_1,…,R_m.  We refer to the set of vertices incident to a hyperedge C_i by f(C_i).  Given a set S⊆{C_1,…,C_n} of hyperedges, we consider ⋃_{C∈S} f(C).  (Not ∑, but ⋃.)  How can we find a set S of s hyperedges that maximizes |⋃_{C∈S} f(C)|?  → Maximum cover!  Although the statement of the question is far from clear, I am reasonably sure that this interpretation is correct.
Tsuyoshi Ito
CC BY-SA 2.5
2011-01-28T17:31:54.783Z
Thanks, Tsuyoshi; that seems plausible.  But if your interpretation is correct, this is not a research-level question.  Vote to close.
Jeffε
CC BY-SA 2.5
2011-01-28T21:58:43.023Z
@JeffE: The only reason I have not done so is because the second question is completely incoherent to me and I cannot tell whether it is too basic or not.  I am waiting for the asker to rephrase the question or for someone to decipher that question.  Given that Yuval managed to decipher the first question (which also looked incoherent to me), I cannot rule out the possibility that someone might be able to understand the second question as well.  If nothing happens in a while, I will vote to close the question.
Tsuyoshi Ito
CC BY-SA 2.5
2011-01-30T10:20:13.633Z
Voted to close the question as [off topic](http://meta.cstheory.stackexchange.com/questions/663/what-does-closed-as-off-topic-mean).  I think that I have waited enough.  See my previous comment (the reply to JeffE) for more detail.
Tsuyoshi Ito
<ds.algorithms>
Find subset of configurations which produces maximum result
Callum
# Find subset of configurations which produces maximum result

(Asked by: username_0 on 2011-01-27)

Given a set of $n$ configurations $C\_1 , C\_2 ... C\_n$ and a function $f$ such that $f(C\_i)$ produces a set of $m$ results $R\_1, R\_2 ... R\_m$ where $R\_j=\{0,1\}$

We only care about the $\Sigma f(C\_i)$ - i.e. $Rj = 1$ if any $f(C\_i)$ has $R\_j = 1$

What is an efficient algorithm to find a subset of $C$ of size $s$ such that a maximum number of $R\_j = 1$ are found?

A secondary problem is to have the subset sorted such that new $R\_j = 1$ are found first. i.e $f(C\_{i+1})$ will find $\leq$ new $R\_j = 1$ than $f(C\_i)$

**Tags:** ds.algorithms
> **Comments:**
> **username_1**: What is the relationship between $C$ and the $C_i$? What is the relationship between $R$ and the $R_i$?  
> **username_0**: Updated to clarify that $C_i$ and $R_j$ are particular instances of $C$ and $R$  
> **username_2**: After reading Yuval’s answer, I understand the first question is about the maximum cover problem.  I still have no idea what the second question means.  
> **username_3**: Sorry, but I find this question completely incoherent.  If R_j = {0,1} for all j, then the "set of m results" R_1, R_2, ..., R_m is actually just a set of one result: {{0,1}}.  That can't be right.  So which one is R_j, and what does R_i equal when i≠j?  What does it mean for f(C_i) to  "produce" a set of results, or for f(C_i) to "have" R_j = 1?  (Unlike Tsuyoshi, I can't mentally massage the problem statement into anything resembling maximum cover.)  
> **username_2**: @JeffE: My interpretation of the question (which was only possible after reading Yuval’s answer) is the following.  f is a hypergraph with n hyperedges labeled C_1,…,C_n and m vertices labeled R_1,…,R_m.  We refer to the set of vertices incident to a hyperedge C_i by f(C_i).  Given a set S⊆{C_1,…,C_n} of hyperedges, we consider ⋃_{C∈S} f(C).  (Not ∑, but ⋃.)  How can we find a set S of s hyperedges that maximizes |⋃_{C∈S} f(C)|?  → Maximum cover!  Although the statement of the question is far from clear, I am reasonably sure that this interpretation is correct.  
> **username_3**: Thanks, Tsuyoshi; that seems plausible.  But if your interpretation is correct, this is not a research-level question.  Vote to close.  
> **username_2**: @JeffE: The only reason I have not done so is because the second question is completely incoherent to me and I cannot tell whether it is too basic or not.  I am waiting for the asker to rephrase the question or for someone to decipher that question.  Given that Yuval managed to decipher the first question (which also looked incoherent to me), I cannot rule out the possibility that someone might be able to understand the second question as well.  If nothing happens in a while, I will vote to close the question.  
> **username_2**: Voted to close the question as [off topic](http://meta.cstheory.stackexchange.com/questions/663/what-does-closed-as-off-topic-mean).  I think that I have waited enough.  See my previous comment (the reply to JeffE) for more detail.  

---

## 1 answers

### Answer by username_4 on 2011-01-27. Score: 3

This problem is known as MAX-COVER. A good algorithm for MAX-COVER is the greedy algorithm: at each stage, we pick a set which maximizes the number of uncovered elements. This algorithm produces a cover of size $s$ which covers a fraction of $1-1/e$ of the optimum. Feige proved that it is NP-hard to outperform this algorithm by any constant.


---

