1
$\begingroup$

For a set of sets $A$, let $\cup A := \cup_{S \in A} S$.

Consider the following problem:

Input:

  • a list of $m$ weights $w = (w_1, \ldots, w_m)$,
  • a list of $n$ distinct subsets $T = (S_1, \ldots, S_n)$ such that $\bigcup_{S\in T} S = [m]$,
  • an integer $k$.

Let $P$ be a partition of $T$. We say $P$ is a $k$-good partition when the size of each part is at most $k$: $\forall p \in P \ |p| \leq k$. The cost of $P$ is defined as the sum of weight of items counted once for each part they appear in, i.e. $$cost(P) := \sum_{p\in P} \ \sum_{x\in \cup p} w_x $$

Output: a $k$-good partition of $P$ of $T$ minimizing $cost(P)$.

What is the complexity of this problem?
Is it NP-hard or is there a polynomial-time algorithm?


Example:
$m = 7$, $w=(2,2,3,4,1,2,2)$,
$n = 3$, $T=(S_1=\{1,2,3\}, S_2=\{3,4,5\}, S_3=\{5,6,7\})$
$k=2$

In this case, since $k<|T|$, it is obvious that more than one partition is 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 optimal $P$ is $\{S_1, S_2\}, \{S_3\}$ with the total cost 12+5=17.


The unweighted version (when the weights of the elements are all 1) is also very interesting to me.

$\endgroup$
  • $\begingroup$ An easy statement about the complexity is to reduce from Weighted Set Cover by simply setting $k=|S|$. $\endgroup$ – chazisop Mar 28 '16 at 6:37
  • $\begingroup$ If I understand your question correctly, you're asking for an algorithm to solve the weighted set cover problem with bounded size, $k$. If you solve the normal weighted set cover problem and find that the minimum cover $C$ requires size $k'$, then don't you simply use $C$ if $k' \leq k$ and declare no solution otherwise? $\endgroup$ – Lawrence Mar 28 '16 at 11:07
  • $\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 13:01
  • $\begingroup$ My understanding is as follows. You have $S = \{S_1, S_2, ... S_m\}$. A configuration is a subset of $S$ with size $\leq k$. The cost of a configuration $C$ is $\sum_{x \in \bigcup C} w(x)$. You want to find a collection of $\leq |U|$ configurations minimizing $\sum_i cost(C_i)$ subject to $\bigcup \bigcup_i C_i = U$. If my understanding is correct, then setting $k=1$ and $w(x)=1$ everywhere means that your cost will be exactly $|U|$ iff the system has an exact cover, doesn't it? It shouldn't get any easier for larger $k$, but that takes an argument that won't fit in the 3 characters left. $\endgroup$ – Yonatan N Mar 28 '16 at 13:58
  • 1
    $\begingroup$ Even after the clarifying remarks, I don't understand the statement of the problem. $\endgroup$ – Neal Young Mar 29 '16 at 2:39
1
$\begingroup$

I believe it's NP-hard, by a reduction from min-balanced cut. Given a graph $G=(V,E)$ and integer $\ell$, min-balanced cut asks whether there is a cut that is balanced (has $|V|/2$ vertices on each side), and cuts at most $\ell$ edges. Given $G$ and $\ell$, construct the following instance of your problem. For each vertex $v$, create a set $S_v$ containing the edges incident to $v$. Take $k=|V|/2$. Then the (minimal) $k$-good partitions are partitions of the sets into two equal-size groups, corresponding to the balanced cuts of $G$, and your (unweighted) cost for such a solution equals $|E|$ plus the number of edges cut. Unless I'm mistaken :-).

EDIT: Similarly you can reduce the following problem to yours: given a graph $G=(V,E)$ and integer $\ell$, color the vertices of $G$ so that each color class has at most $k$ vertices, minimizing the number of edges whose two endpoints have the same color. (The reduction: make a set $S_v$ for each vertex $v\in V$, containing the pairs $\{v,w\}$ not in $E$.)

$\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.