Suppose we have a set $S = \{(a_1,b_1),...,(a_n,b_n)\}$ where $a_i < m$, $b_i = m-a_i$, $m \in \mathbb{Z}^{+}$, $m>2$ and $n$ is an even number greater than $3$. What is the most efficient algorithm to determine if it is possible to partition $S$ into two distinct subsets, $C$ and $D$, of equal size such that

$\sum_{a \in C} a > \sum_{b \in C} b$   and   $\sum_{a \in D} a > \sum_{b \in D} b$

or  $\sum_{b \in C} b > \sum_{a \in C} a$  and  $\sum_{b \in D} b > \sum_{a \in D} a$  ?

For example, if $S = \{(56,44),(48,52),(43,57),(60,40)\}$, $C = \{(56,44),(48,52)\}$, and $D = \{(43,57),(60,40)\}$.

I am considering iteratively matching a pair with the best value of $a$ with a pair with the worst value of $a$. Is there another algorithm?

  • 1
    $\begingroup$ If you start by computing $A=\sum_i a_i$ and $B=\sum_i b_i$, then if $A>B$ then only the first case is possible, and if $A<B$ only the second case is possible. So the problem can be stated by adding the condition $A>B$, and just considering the first case. I think it's a cleaner formulation. $\endgroup$
    – Shaull
    Feb 22, 2013 at 11:26

1 Answer 1


If I understood well the problem:

$S = \{ (a_1, m-a_1), (a_2, m-a_2), ..., (a_n, m-a_n),\; m>2 $

$\sum_{a_i \in C} a_i > \sum_{a_i \in C} (m - a_i)$ and $\sum_{a_j \in D} a_j > \sum_{a_j \in D} (m - a_j)$ is equivalent to

$\sum_{a_i \in C} a_i > m * |C| - \sum_{a_i \in C} a_i$ and $\sum_{a_j \in D} a_j > m * |D| - \sum_{a_j \in D} a_j$ is equivalent to

$2 * \sum_{a_i \in C} a_i > m * |C|$ and $2 * \sum_{a_j \in D} a_j > m * |D|$ is equivalent to

$2 * \sum_{a_i \in C} a_i > m * |S| / 2$ and $2 * \sum_{a_j \in D} a_j > m * |S| / 2$ is equivalent to

$4 * \sum_{a_i \in C} a_i > m * |S|$ and $4 * \sum_{a_j \in D} a_j > m * |S|$

Then given an instance of the PARTITION problem $\Pi$, $S = \{ a_1, ..., a_n \}, \sum a_i = 2k$

Add two equal big integers $z >> k$ such that $z = t * (|S|+2) - k + 1$; the equivalent partition problem $\Pi'$ is $S' = S \cup \{a_{n+1}=z, a_{n+2}=z\}$, $\sum = 2(k+z)$ i.e. the sum of the elements of the two equal partitions must be equal to $k+z$

Now you can set $m = 4*((k+z)-1)/|S'|$ which is an integer: $m = 4 * ( k + t*|S'| - k + 1 - 1)/|S'| = 4 * (t - 1) * |S'|$ and your problem inequalities become:

$\sum_{a_i \in C} a_i > k+z-1$ and $\sum_{a_j \in D} a_j > k + z - 1$

And it have a solution if and only if $\Pi'$ has a solution.

  • $\begingroup$ To summarize: your problem seems to be NP-hard. However, that does not answer the question after suitable algorithms. $\endgroup$
    – Raphael
    Feb 24, 2013 at 16:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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