2
$\begingroup$

We are given a set of $m$ elements $\{e_1,...,e_m\}$ that form our universe $\mathcal{U}$. Each element of our universe is further associated with a positive weight $w(e_j)$ with $j\in \{1,...m\}$. We are further given a collection $S=\{S_1,...S_n\}$ of subsets of $\mathcal{U}$ whose union equals the universe. The intersection of any two sets in $S$ may be non-empty (i.e. subsets may overlap with each other).

Furthermore,

1) we are given an infinite number of configurations; each configuration can host up to $k$ subsets from $S$. There is no cost for using a configuration.

2) When assigning 2 or more subsets to one configuration and there is an overlap between the sets (i.e. an element is part of more than one set) we pay the weight of that element only once. Obviously, there can be no overlap between subsets when considering different configurations.

Objective:

we want to assign each subset of $S$ to exactly one configuration in such a way that the weighted sum of the elements over all configurations is minimized. Consider the following example:

$\mathcal{U}=\{a,b,c,d,e,f,g\}$,

$w(a)=2$

$w(b)=2$

$w(c)=3$

$w(d)=4$

$w(e)=1$

$w(f)=2$

$w(g)=2$

$S=\{S_1, S_2, S_3\},$

$S_1=\{a,b,c\}, S_2=\{c,d,e\}, S_2=\{e,f,g\}$

$k=2$

In this case, since $k<|S|$, it is obvious that more than one configurations are needed. Moreover, $S_1$ and $S_2$ should be packed together in the same configuration because of their heavy overlap ($S_1 \cap S_2$ gives the biggest overlap in our example - we pay 3 less cost units). So, the total cost of such an assignment is 12+5=17 and 2 configurations are needed.

Any ideas on how to prove that the problem is indeed intractable? Any ideas on how to calculate a good bound on the number of configurations that are needed?

The unweighted version (when the weights of the elements are all 1) is also very interesting to me. However, I did not manage to find something so far in the literature also for this problem.

Thank you!

$\endgroup$
  • $\begingroup$ I don't understand the problem you're trying to solve. What objects are weighted? What does it mean to minimize "in multiple configurations"? When $|S|=10$ and $k=4$, why are there three configurations? Whatever all those things mean, isn't the problem exactly the classical set cover problem when you set all the weights equal to 1 and have only one configuration? If set cover really is a special case, and your problem is still in NP (which should be trivial to prove), then your problem is automatically NP-complete. $\endgroup$ – David Richerby Mar 28 '16 at 5:38
  • $\begingroup$ Please give an example. As stated, your problem is hard to understand. Also, as David mentions, perhaps the best you can do is use approximation algorithms or heuristics. $\endgroup$ – Yuval Filmus Mar 28 '16 at 8:15
  • $\begingroup$ Thank you for your answers. I tried to come up with a better description of my problem. Hope that the new description is much clearer. $\endgroup$ – Christos AMS Mar 28 '16 at 12:59
  • $\begingroup$ cross posted on Theoretical Computer Science. $\endgroup$ – Kaveh Apr 30 '16 at 0:53
1
$\begingroup$

When $k=1$, the problem is trivial: the optimal solution is to put each set in its own configuration.

When $k=2$, the problem can be solved in polynomial time using graph matching. Build a complete undirected graph with one vertex per set. The cost of the edge $(S_i,S_j)$ is the cost of putting $S$ and $T$ together in the same configuration (i.e., the weight of $S_i \cup S_j$). Now the optimal solution to your problem is given by the minimum-cost perfect matching in this graph. That matching can be computed in polynomial time using standard algorithms.

When $k=3$, the problem is NP-hard. In fact, it is NP-hard to determine whether a graph can be covered by a disjoint union of cycles of length $\le 3$ (i.e., whether you can find a set of cycles, where each cycle has length 2 or 3, where no two cycles have any vertex in common, and where every vertex appears in one of these cycles). This implies that your problem is intractible when $k\ge 3$.

The proof of the hardness result I alluded to can be found in Section 3 of the following paper:

Clearing Algorithms for Barter Exchange Markets: Enabling Nationwide Kidney Exchanges. David J Abraham, Avrim Blum, Tuomas Sandholm. EC 2007.

That said, not all hope is lost. There are techniques available for finding a solution that will be close to optimal, using integer linear programming. For instance, you can express your problem as an instance of integer linear programming and then apply an off-the-shelf ILP solver. See the paper above for some more sophisticated techniques that might be applicable in your situation as well.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.