Skip to main content
Theoretical Computer Science

Return to Answer

added 1 character in body
Source Link
Sariel Har-Peled
Sariel Har-Peled
  • 9.6k
  • 33
  • 54

This is a set packing problem under the constraint that for the solution $\mathcal{A}$, for any subset $\mathcal{B} \subseteq \mathcal{A}$, we have that there is always an element in $\bigcup_{X \in \mathcal{B}} X$, which is covered onlyexactly once.

Proof: Given a solution to your problem, it immediately has this property. Indeed, if $E_1, \ldots, E_m$ is the optimal solution to your problem, then consider a subset $\mathcal{B}$ of these sets, and assume $E_i$ is the last set in this sequence appearing in $\mathcal{B}$. By the required property that the solution is incremental, it follows that $E_i$ covers an element that no prior set covers, which implies the above property.

As for the other direction, it also easy. Start from the solution $\mathcal{A}$, find the element that is covered exactly once, set it sets as the last set in the sequence, remove this set, and repeat. QED.

This is a pretty natural problem....

Quick reminder: In the set packing problem, given a family of sets, find the maximal subset of sets, that comply with some additional constraint (say, no element is covered more than 10 times, etc).

This is a set packing problem under the constraint that for the solution $\mathcal{A}$, for any subset $\mathcal{B} \subseteq \mathcal{A}$, we have that there is always an element in $\bigcup_{X \in \mathcal{B}} X$, which is covered only once.

Proof: Given a solution to your problem, it immediately has this property. Indeed, if $E_1, \ldots, E_m$ is the optimal solution to your problem, then consider a subset $\mathcal{B}$ of these sets, and assume $E_i$ is the last set in this sequence appearing in $\mathcal{B}$. By the required property that the solution is incremental, it follows that $E_i$ covers an element that no prior set covers, which implies the above property.

As for the other direction, it also easy. Start from the solution $\mathcal{A}$, find the element that is covered exactly once, set it sets as the last set in the sequence, remove this set, and repeat. QED.

This is a pretty natural problem....

Quick reminder: In the set packing problem, given a family of sets, find the maximal subset of sets, that comply with some additional constraint (say, no element is covered more than 10 times, etc).

This is a set packing problem under the constraint that for the solution $\mathcal{A}$, for any subset $\mathcal{B} \subseteq \mathcal{A}$, we have that there is always an element in $\bigcup_{X \in \mathcal{B}} X$, which is covered exactly once.

Proof: Given a solution to your problem, it immediately has this property. Indeed, if $E_1, \ldots, E_m$ is the optimal solution to your problem, then consider a subset $\mathcal{B}$ of these sets, and assume $E_i$ is the last set in this sequence appearing in $\mathcal{B}$. By the required property that the solution is incremental, it follows that $E_i$ covers an element that no prior set covers, which implies the above property.

As for the other direction, it also easy. Start from the solution $\mathcal{A}$, find the element that is covered exactly once, set it as the last set in the sequence, remove this set, and repeat. QED.

This is a pretty natural problem....

Quick reminder: In the set packing problem, given a family of sets, find the maximal subset of sets, that comply with some additional constraint (say, no element is covered more than 10 times, etc).

Source Link
Sariel Har-Peled
Sariel Har-Peled
  • 9.6k
  • 33
  • 54

This is a set packing problem under the constraint that for the solution $\mathcal{A}$, for any subset $\mathcal{B} \subseteq \mathcal{A}$, we have that there is always an element in $\bigcup_{X \in \mathcal{B}} X$, which is covered only once.

Proof: Given a solution to your problem, it immediately has this property. Indeed, if $E_1, \ldots, E_m$ is the optimal solution to your problem, then consider a subset $\mathcal{B}$ of these sets, and assume $E_i$ is the last set in this sequence appearing in $\mathcal{B}$. By the required property that the solution is incremental, it follows that $E_i$ covers an element that no prior set covers, which implies the above property.

As for the other direction, it also easy. Start from the solution $\mathcal{A}$, find the element that is covered exactly once, set it sets as the last set in the sequence, remove this set, and repeat. QED.

This is a pretty natural problem....

Quick reminder: In the set packing problem, given a family of sets, find the maximal subset of sets, that comply with some additional constraint (say, no element is covered more than 10 times, etc).