<p>I have this problem:</p>

<p>Given a collection of sets $S:\{S_{1},...,S_{k}\}$ where each set $S_{j}$ is a subset of $U:\{e_{1},...,e_{n}\}$ universe of elements. I would find-out a subset $C \subseteq S$ such that I maximize the function $f(C)=|\cup_{\forall C_{j} \in C} C_{j}|$ and minimize the function $g(C)=\sum_{\forall C_{j},C_{i} \in C}|C_{i} \cap C_{j}|$.</p>

<p>I have found out a Integer Linear Programming formulation for this problem, now I'm wondering is this problem NP-Hard?  Does exist in literature a similar problem?</p>

<p>My formulation: </p>

<p>$max(\sum_{\forall e}e_{j} - k \sum_{\forall z}z_{j})$</p>

<p>$\forall e_{j} \in U: \;\;e_{j} \leq \sum_{\forall S_{i}\;s.t.\; e_{j} \in S_{i}}s_{i}$</p>

<p>$\forall e_{j} \in S_{j} \;s.t.\; e_{j} \in S_{k} \cap S_{t}:\;\;  z_{j} \geq s_{k}+s_{t}-1$</p>

<p>all variable in ${0,1}$, k is a constant to specify the malus for adding an overlap.</p>

<p>The problem formulated in this way can solve Maximum Set Packing. So it is NP-Hard.
Now I'm wondering what can be a good heuristic to find some solutions?
I'm trying a greedy algorithm that put at each step the elements with the maximum ratio of new covered elements over new intersections.</p>

CC BY-SA 3.0
2011-09-13T22:36:24.177Z
How do you express this bicriteria problem as an ILP ? do you minimize g - f or something ?
Suresh Venkat
CC BY-SA 3.0
2011-09-14T14:43:31.543Z
I'm curious about the ILP formulation.  I think the formulation itself could make the problem clearer.
Yoshio Okamoto
CC BY-SA 3.0
2011-09-14T16:03:45.777Z
The notation does not make sense. One cannot sum over elements in the sets. The standard way to phrase this kind of bi-criteria problem is to put a bound on one function and optimize the other. One natural special case here is to maximize the number of covered elements such that the chosen sets have no overlap, that is, they are disjoint. This is NP-Hard from an easy reduction from Exact-3-Cover (which is essentially the same as 3-Dimensional-Matching).
Chandra Chekuri
CC BY-SA 3.0
2011-09-14T17:06:35.253Z
I think the OP meant to define f(C) as the sum of |S_j| and g(C) as the sum of |I_k|.
Suresh Venkat
CC BY-SA 3.0
2011-09-17T15:43:55.213Z
@user6537: You should merge the two accounts (assuming that the two accounts with different names really belong to the same person).  Please see [this post on Meta Stack Overflow](http://meta.stackexchange.com/questions/18232/how-can-one-link-merge-combine-associate-two-accounts-users-anonymous-unregiste/73801#73801) for the instructions.
Tsuyoshi Ito
<cc.complexity-theory><np-hardness>
Maximize Covering Minimizing the Overlap
Federico Milotti
# Maximize Covering Minimizing the Overlap

(Asked by: username_0 on 2011-09-13)

I have this problem:

Given a collection of sets $S:\{S\_{1},...,S\_{k}\}$ where each set $S\_{j}$ is a subset of $U:\{e\_{1},...,e\_{n}\}$ universe of elements. I would find-out a subset $C \subseteq S$ such that I maximize the function $f(C)=|\cup\_{\forall C\_{j} \in C} C\_{j}|$ and minimize the function $g(C)=\sum\_{\forall C\_{j},C\_{i} \in C}|C\_{i} \cap C\_{j}|$.

I have found out a Integer Linear Programming formulation for this problem, now I'm wondering is this problem NP-Hard? Does exist in literature a similar problem?

My formulation:

$max(\sum\_{\forall e}e\_{j} - k \sum\_{\forall z}z\_{j})$

$\forall e\_{j} \in U: \;\;e\_{j} \leq \sum\_{\forall S\_{i}\;s.t.\; e\_{j} \in S\_{i}}s\_{i}$

$\forall e\_{j} \in S\_{j} \;s.t.\; e\_{j} \in S\_{k} \cap S\_{t}:\;\; z\_{j} \geq s\_{k}+s\_{t}-1$

all variable in ${0,1}$, k is a constant to specify the malus for adding an overlap.

The problem formulated in this way can solve Maximum Set Packing. So it is NP-Hard.
Now I'm wondering what can be a good heuristic to find some solutions?
I'm trying a greedy algorithm that put at each step the elements with the maximum ratio of new covered elements over new intersections.

**Tags:** cc.complexity-theory, np-hardness
> **Comments:**
> **username_1**: How do you express this bicriteria problem as an ILP ? do you minimize g - f or something ?  
> **username_2**: I'm curious about the ILP formulation.  I think the formulation itself could make the problem clearer.  
> **username_3**: The notation does not make sense. One cannot sum over elements in the sets. The standard way to phrase this kind of bi-criteria problem is to put a bound on one function and optimize the other. One natural special case here is to maximize the number of covered elements such that the chosen sets have no overlap, that is, they are disjoint. This is NP-Hard from an easy reduction from Exact-3-Cover (which is essentially the same as 3-Dimensional-Matching).  
> **username_1**: I think the OP meant to define f(C) as the sum of |S_j| and g(C) as the sum of |I_k|.  
> **username_4**: @user6537: You should merge the two accounts (assuming that the two accounts with different names really belong to the same person).  Please see [this post on Meta Stack Overflow](http://meta.stackexchange.com/questions/18232/how-can-one-link-merge-combine-associate-two-accounts-users-anonymous-unregiste/73801#73801) for the instructions.  

---

## 0 answers

