0
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ How do you express this bicriteria problem as an ILP ? do you minimize g - f or something ? $\endgroup$ – Suresh Venkat Sep 13 '11 at 22:36
  • $\begingroup$ I'm curious about the ILP formulation. I think the formulation itself could make the problem clearer. $\endgroup$ – Yoshio Okamoto Sep 14 '11 at 14:43
  • 2
    $\begingroup$ 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). $\endgroup$ – Chandra Chekuri Sep 14 '11 at 16:03
  • $\begingroup$ I think the OP meant to define f(C) as the sum of |S_j| and g(C) as the sum of |I_k|. $\endgroup$ – Suresh Venkat Sep 14 '11 at 17:06
  • $\begingroup$ @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 for the instructions. $\endgroup$ – Tsuyoshi Ito Sep 17 '11 at 15:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.