Optimal partition of a set of pairs

Question

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?

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.