<p>If the required number of times we need to cover an element is 2, we have the following <em>densest k-subgraph problem</em>: (Imagine the edges are elements and nodes are sets.)</p>
<blockquote>
<p>Given a graph <span class="math-container">$G$</span> and an integer <span class="math-container">$k$</span>, find a subgraph of <span class="math-container">$G$</span> on <span class="math-container">$k$</span> nodes with maximum density.</p>
</blockquote>
<p>Khot proved that <a href="https://ieeexplore.ieee.org/document/1366233" rel="nofollow noreferrer">no PTAS exists under plausible complexity assumptions</a>; there is <a href="http://www.cs.princeton.edu/%7Earavindv/DkS.pdf" rel="nofollow noreferrer">an <span class="math-container">$O(n^{1/4+\epsilon})$</span> approximation</a> to the problem by Bhaskara, Charikar, Chlamtac, Feige and Vijayaraghavan; <a href="http://www.cs.princeton.edu/%7Earavindv/dksgaps.pdf" rel="nofollow noreferrer">a polynomial integrality gaps result</a> by Bhaskara, Charikar, Guruswami, Vijayaraghavan and Zhou.  Therefore I believe your question is hard to approximate in the most general case.</p>

CC BY-SA 4.0
2022-06-28T03:24:21.757Z
Hardness for Densest k-subgraph has been substantially improved under ETH. https://arxiv.org/abs/1611.05991
Chandra Chekuri
CC BY-SA 4.0
2013-12-22T04:58:09.660Z
2022-06-27T10:06:48.610Z
2022-06-27T10:06:48.610Z
Hsien-Chih Chang 張顯之
<p>In the set multicover problem we are given a set N of n elements and a set S of m subsets of N. Additionally, each element has a coverage requirement, i.e. the number of times it has to be covered. The question is to cover N with the minimum number of subsets from S. I'm aware of the approximation algorithms for this problem (Rajagopalan &amp; Vazirani).</p>

<p>I'm interested in a different version of the problem (max multi-coverage). We are given K and we ask for the maximal number of the elements from N we can cover with K subsets from S. We count an element as covered if it is covered at least the required number of times. Are there any approximation algorithms for this case? Are there any lower bounds for this case (or even for the standard set multicover problem)?</p>

<p>Thanks in advance!</p>

CC BY-SA 3.0
2013-12-22T04:52:20.077Z
Do you have any constrains on the set system?
Hsien-Chih Chang 張顯之
<set-cover><approximation>
Approximating Max-Coverage when the elements need to be covered multiple times
Piotr Skowron
# Approximating Max-Coverage when the elements need to be covered multiple times

(Asked by: username_0 on 2013-12-21)

In the set multicover problem we are given a set N of n elements and a set S of m subsets of N. Additionally, each element has a coverage requirement, i.e. the number of times it has to be covered. The question is to cover N with the minimum number of subsets from S. I'm aware of the approximation algorithms for this problem (Rajagopalan & Vazirani).

I'm interested in a different version of the problem (max multi-coverage). We are given K and we ask for the maximal number of the elements from N we can cover with K subsets from S. We count an element as covered if it is covered at least the required number of times. Are there any approximation algorithms for this case? Are there any lower bounds for this case (or even for the standard set multicover problem)?

Thanks in advance!

**Tags:** set-cover, approximation

> **Comments:**
> **username_1**: Do you have any constrains on the set system?  

---

## 1 answers

### Answer by username_1 on 2013-12-22. Score: 6 | Accepted answer

If the required number of times we need to cover an element is 2, we have the following *densest k-subgraph problem*: (Imagine the edges are elements and nodes are sets.)

> Given a graph $G$ and an integer $k$, find a subgraph of $G$ on $k$ nodes with maximum density.

Khot proved that [no PTAS exists under plausible complexity assumptions](https://ieeexplore.ieee.org/document/1366233); there is [an $O(n^{1/4+\epsilon})$ approximation](http://www.cs.princeton.edu/%7Earavindv/DkS.pdf) to the problem by Bhaskara, Charikar, Chlamtac, Feige and Vijayaraghavan; [a polynomial integrality gaps result](http://www.cs.princeton.edu/%7Earavindv/dksgaps.pdf) by Bhaskara, Charikar, Guruswami, Vijayaraghavan and Zhou. Therefore I believe your question is hard to approximate in the most general case.

> **Comments:**
> **username_2**: Hardness for Densest k-subgraph has been substantially improved under ETH. https://arxiv.org/abs/1611.05991  

---

