Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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?

share|improve this question
1  
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. –  Shaull Feb 22 '13 at 11:26
add comment

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.

share|improve this answer
    
To summarize: your problem seems to be NP-hard. However, that does not answer the question after suitable algorithms. –  Raphael Feb 24 '13 at 16:10
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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