Suppose I have a set of $2N$ items with weights $w_0, w_1, \ldots, w_{2N-1}$. I want to identify the two most "balanced" sets of $k$ items each, where $k$ is not given but limited to the range $k_\min \leq k \leq N$.

More specifically: Identify the two disjunct subsets $A = \{a_0, a_1, \ldots a_{k-1}\}$ and $B = \{b_0, b_1, \ldots a_{k-1}\}$ subject to the following conditions:

  • all the $a_i, b_i \in [0,2N-1]$
  • $A \cap B = \varnothing$
  • both sets have equal cardinality $k$ where $k_\min \leq k \leq N$
  • the following quantity $\epsilon$ is minimized: $$ \begin{align} \epsilon &= \frac{|W_A-W_B|}{W_A+W_B} \cr W_A &= \sum\limits_{i=0}^{k-1}w_{a_i} \cr W_B &= \sum\limits_{i=0}^{k-1}w_{b_i} \cr \end{align}$$

Is this a known problem? (I found Is there a "balanced knapsacks" problem with a known result? which is similar)

In my case the value of $N$ is not very large (under 50) so I don't really care about proving NP-hard, I just want to know a good strategy.


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.