<p>We can abstract this problem as submodular minimization (minimize additional covers) under submodular cover (set cover) constraint. I'll point you towards two papers in this area.</p>
<ul>
<li>Iwata and Nagano, 2009. Submodular function minimization under covering constraints. <a href="https://ieeexplore.ieee.org/abstract/document/5438589" rel="nofollow noreferrer">https://ieeexplore.ieee.org/abstract/document/5438589</a></li>
<li>Kamiyama, 2011. Submodular function minimization under a submodular set covering constraint. <a href="https://link.springer.com/chapter/10.1007/978-3-642-20877-5_14" rel="nofollow noreferrer">https://link.springer.com/chapter/10.1007/978-3-642-20877-5_14</a></li>
</ul>
<p>The first paper proves that a primal-dual algorithm achieves constant approximation if maximum frequency is fixed. The second paper gives a more careful bound.</p>

CC BY-SA 4.0
2023-12-04T00:46:27.777Z
The Iwata and Nagano paper proves a strong lower bound on the approximation when the maximum frequency is not bounded. The lower bound should probably hold for the OPs problem as well.
Chandra Chekuri
CC BY-SA 4.0
2023-12-03T06:03:19.460Z
2023-12-03T06:03:19.460Z
darwinflinches
<p>Consider the following variant of set cover:</p>
<p>Given: Target set <span class="math-container">$T$</span> and a collection of sets <span class="math-container">$\mathcal{C}$</span>, such that <span class="math-container">$T \subseteq \bigcup_{C \in \mathcal{C}} C$</span>.</p>
<p>Wanted: A subset <span class="math-container">$\mathcal{C'}$</span> of <span class="math-container">$\mathcal{C}$</span>, such that <span class="math-container">$T \subseteq \bigcup_{C \in \cal{C'}} C$</span> and <span class="math-container">$|\bigcup_{C \in \cal{C'}} C|$</span> is minimal.</p>
<p>In other words, we are looking for a covering of <span class="math-container">$T$</span> that covers as few additional elements as possible.</p>
<p>It is relatively easy to see that this problem is NP-complete.</p>
<p>Is this a known problem? What is its name?</p>

CC BY-SA 4.0
2023-11-08T20:42:38.670Z
One of the standard generalizations of Set Cover is _minimizing a linear function subject to a submodular constraint_.  See e.g. https://algnotes.info/on/background/set-cover-wolsey/ .  Doesn't look like it quite captures your problem though.
Neal Young
CC BY-SA 4.0
2023-11-08T21:29:03.377Z
Ouch, indeed the $\sum$'s should be $\bigcup$'s.
Jan Reineke
<set-cover>
Known Variant of Set Cover?
Jan Reineke
# Known Variant of Set Cover?

(Asked by: username_0 on 2023-11-08)

Consider the following variant of set cover:

Given: Target set $T$ and a collection of sets $\mathcal{C}$, such that $T \subseteq \bigcup\_{C \in \mathcal{C}} C$.

Wanted: A subset $\mathcal{C'}$ of $\mathcal{C}$, such that $T \subseteq \bigcup\_{C \in \cal{C'}} C$ and $|\bigcup\_{C \in \cal{C'}} C|$ is minimal.

In other words, we are looking for a covering of $T$ that covers as few additional elements as possible.

It is relatively easy to see that this problem is NP-complete.

Is this a known problem? What is its name?

**Tags:** set-cover
> **Comments:**
> **username_1**: One of the standard generalizations of Set Cover is _minimizing a linear function subject to a submodular constraint_.  See e.g. https://algnotes.info/on/background/set-cover-wolsey/ .  Doesn't look like it quite captures your problem though.  
> **username_0**: Ouch, indeed the $\sum$'s should be $\bigcup$'s.  

---

## 1 answers

### Answer by username_2 on 2023-12-03. Score: 3

We can abstract this problem as submodular minimization (minimize additional covers) under submodular cover (set cover) constraint. I'll point you towards two papers in this area.

* Iwata and Nagano, 2009. Submodular function minimization under covering constraints. <https://ieeexplore.ieee.org/abstract/document/5438589>
* Kamiyama, 2011. Submodular function minimization under a submodular set covering constraint. <https://link.springer.com/chapter/10.1007/978-3-642-20877-5_14>

The first paper proves that a primal-dual algorithm achieves constant approximation if maximum frequency is fixed. The second paper gives a more careful bound.

> **Comments:**
> **username_3**: The Iwata and Nagano paper proves a strong lower bound on the approximation when the maximum frequency is not bounded. The lower bound should probably hold for the OPs problem as well.  

---

