(Pardon me for any unrefined usage/terminology for I do not have a math/CS background.) Consider a collection of $N$ balls with subsets of $n_1, n_2, ..., n_L$ balls of different $L$ colors. The problem is to partition the $N$ balls into $M$ equal-sized groups (given $(N\mod M)=0$) such that the color subsets are preserved within new groups as much as possible. In the scenarios I'm concerned with, you could assume that for all $L$ original subsets, $n_l < (N/M)$.

Here's an example to make the problem clear: For a collection of $12$ balls with $4$ color-subsets - $\{1111\}$, $\{222\}$, $\{33\}$, $\{444\}$ - that needs to be split into 2 groups, the best way to do so is $\{111133\}$ and $\{222444\}$

  1. Is this problem well-defined?
  2. Is there an algorithm to solve this problem exactly in polynomial time?
  3. If not, is there an approximate algorithm?
  • 2
    $\begingroup$ I think you'll need to be precise about "preserved as much as possible". Is there a penalty function ? $\endgroup$ – Suresh Venkat Nov 10 '11 at 22:56
  • $\begingroup$ I do not have any concrete penalty function in mind, except that this function has to be an increasing function of the number (and size?) of splits of the same-colored subsets. For instance, a subset of 10 blue balls is could receive increasing penalty in the following order: {10} < {9,1} < {8,2} <(?) {8,1,1} < ... I see that this may be related to partition functions, but I'm not sure. $\endgroup$ – Arjun Krishnan Nov 17 '11 at 23:25
  • $\begingroup$ that's not really enough. I think just for clarity you need to define for a given solution how to compute its cost. it doesn't have to be exactly what you had in mind as long as it emphasizes the right "trends" $\endgroup$ – Suresh Venkat Nov 18 '11 at 4:36

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.