<p>Take an arbitrary instance <span class="math-container">$S_1,\ldots,S_n$</span> of SET COVER. Between <span class="math-container">$S_1$</span> and <span class="math-container">$S_2$</span>, insert a chain of new subsets
<span class="math-container">$$ S_1-x,~ S_1-\{x,y\},~ \ldots,~ \{z\},~ \emptyset,~ \{c\},~ \ldots,~ S_2-\{a,b\},~ S_2-\{a\}.$$</span>
Do the same for all other pairs of consecutive sets.</p>
<p>The resulting instance satisfies your condition, and it is equivalent (with respect to complexity and with respect to approximability) to the original instance.</p>

CC BY-SA 4.0
2021-06-23T12:16:42.007Z
2021-06-23T12:16:42.007Z
Gamow
<p>First I define my version of the set cover problem: We have a collection of sets such as <span class="math-container">$S_1, \dots, S_m$</span> where each <span class="math-container">$S_i$</span> is a subset of <span class="math-container">$M=\{1,\dots, m\}$</span>. The goal is to find the minimum number of <span class="math-container">$S_i$</span>'s where their union is equal to <span class="math-container">$M$</span>. This is my standard version of set cover.</p>
<p>Now, suppose each two consecutive set <span class="math-container">$S_i$</span> and <span class="math-container">$S_{i+1}$</span> in our problem differ in at most one item, i.e., <span class="math-container">$\big||S_i|-|S_{i-1}|\big| \leq 1$</span> and either <span class="math-container">$S_i\subseteq S_{i+1}$</span> or <span class="math-container">$S_i\subseteq S_{i+1}$</span>. Does this assumption make the set cover easier to approximate (in polynomial-time)?</p>

CC BY-SA 4.0
2021-06-23T13:16:38.130Z
FYI, the problem in your first paragraph is called Set Cover, not Subset Sum.  This seems like a nice homework exercise.
Neal Young
CC BY-SA 4.0
2021-06-23T18:14:41.710Z
Thank you. Subset sum was a type. Only the title was correct! By the way, it was not a homework, but it is indeed a suitable question for an exercise.
Mohemnist
<ds.algorithms><approximation-algorithms><approximation-hardness><set-cover><approximation>
Set cover where consecutive sets differ by at most one item
Mohemnist
# Set cover where consecutive sets differ by at most one item

(Asked by: username_0 on 2021-06-23)

First I define my version of the set cover problem: We have a collection of sets such as $S\_1, \dots, S\_m$ where each $S\_i$ is a subset of $M=\{1,\dots, m\}$. The goal is to find the minimum number of $S\_i$'s where their union is equal to $M$. This is my standard version of set cover.

Now, suppose each two consecutive set $S\_i$ and $S\_{i+1}$ in our problem differ in at most one item, i.e., $\big||S\_i|-|S\_{i-1}|\big| \leq 1$ and either $S\_i\subseteq S\_{i+1}$ or $S\_i\subseteq S\_{i+1}$. Does this assumption make the set cover easier to approximate (in polynomial-time)?

**Tags:** ds.algorithms, approximation-algorithms, approximation-hardness, set-cover, approximation
> **Comments:**
> **username_1**: FYI, the problem in your first paragraph is called Set Cover, not Subset Sum.  This seems like a nice homework exercise.  
> **username_0**: Thank you. Subset sum was a type. Only the title was correct! By the way, it was not a homework, but it is indeed a suitable question for an exercise.  

---

## 1 answers

### Answer by username_2 on 2021-06-23. Score: 1 | Accepted answer

Take an arbitrary instance $S\_1,\ldots,S\_n$ of SET COVER. Between $S\_1$ and $S\_2$, insert a chain of new subsets
$$ S\_1-x,~ S\_1-\{x,y\},~ \ldots,~ \{z\},~ \emptyset,~ \{c\},~ \ldots,~ S\_2-\{a,b\},~ S\_2-\{a\}.$$
Do the same for all other pairs of consecutive sets.

The resulting instance satisfies your condition, and it is equivalent (with respect to complexity and with respect to approximability) to the original instance.


---

