Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Suppose I have $2n$ numbers, from which I will compute $n$ sums of two-number pairs. For example, I have $6$ numbers $(1, 2, 3, 4, 5, 6)$ and I can generate three sums of $1+3=4$, $2+6=8$, and $4+5=9$. Each number has to be used once and only once. There are totally $\frac{(2n)!}{2^n n!}$ possible lists of outcomes. Note that these $2n$ numbers can be any values, not necessarily integers. This is just a simple example for illustration.

My goal is to make these sums as close to my target value as possible on average. Suppose my target value is $7$. If the pairs are $(1, 3), (2, 6), (4, 5)$, their sums are $4, 8, 9$. The difference to my target $7$ is defined as $|4-7|+|8-7|+|9-7|=6$. However, if a different pair lists $(1, 6), (2, 5), (3, 4)$ is used, the difference to the target would be $|7-7|+|7-7|+|7-7|=0$. So the latter setup is closer to the target on average. This is actually the optimal choice in all possible outcomes.

My question is if there is a good computing algorithm to find the optimal choice of pairs, instead of computing all $\frac{(2n)!}{2^n n!}$ possibilities.

BTW: what if the difference on average is defined by sum of squares $(4-7)^2+(8-7)^2+(9-7)^2$?

share|improve this question
    
I am going to go out on a limb and say that matching least with greatest is the best- if any single change is made to that solution, it will always cause an increase in the sum. –  adam W Jan 22 '13 at 5:19
    
@adamW I definitely agree with you, but that argument isn't rigorous at all, as we need to look at all changes and not just single ones. In optimization terms we might have found a local minimum. –  Sam DeHority Jan 22 '13 at 19:16
    
@Doctor I do agree with that as well. The process I can think of to make it rigorous would require some topological type of constructions, and I did not write it up. However, it does have me convinced that the particular local minimum is indeed a global one. –  adam W Jan 22 '13 at 21:44
add comment

2 Answers 2

up vote 2 down vote accepted

It seems to me that if the integers are ordered from $1$ to $2n$, the optimal solution will always be summing the $i^{th}$ integer with integer $2n - i + 1$, basically meaning summing the largest with the smallest and performing this recursively. This is exactly how it turned out in your example.

This makes sense intuitively, because if the target is large, summing two larger numbers together will come closer to the solution but will make the smaller numbers required to be summed together differ from the solution by at least the same amount as gained if not more. The same holds if the target is small, and is analogous if the target is mid-ranged.

share|improve this answer
    
These $2n$ numbers can be any numbers, not necessarily integers. I modified my post. Thank you. –  Patrick Li Jan 22 '13 at 5:09
    
@Patrick The result still holds if the numbers are arbitrary real numbers for the same reason. –  Sam DeHority Jan 22 '13 at 16:27
add comment

Here are my thoughts that are way better than searching exhaustively.

First take your set and shift each, $$(1,2,3,4,5,6) \rightarrow (1-\frac{7}{2}, 2-\frac{7}{2}, \ldots \text{etc})$$ This gives the target value of zero. Now when your set of numbers is shifted in this way, the numbers are easily compared. The largest negative needs be combined with the largest positive, that is the only way to obtain the least error for that large number. This method would easily find the best for your small example. I am not sure, but this maybe is the best way, at least for pairing (if you wanted $3$ and only $3$ instead of $2$ for each sum, I believe that very much complicates things raising the difficulty.)

There is also a matching algorithm (I will let you know if I can remember the name) that I read that works by comparing possible discrete (single) changes, keeping the improvements. Let me attempt a description that may lack good terminology or symbols (sorry).

Basically in your example you start with $(1,3) \quad (2,6) \quad (4,5)$ and look at the $(1,3)$ as it has the most error. Then find if any improvement may be had with re-ordering: \begin{align} (1,3)\Delta 3 & (2,6)\Delta 1 & \Delta_{\text{total}} = 4\\ (1,6)\Delta 0 & (2,3)\Delta 2 & \Delta_{\text{total}} = 2 &\text{improvement- keep} \end{align}

At this point your set is now $$(1,6) \quad (2,3) \quad (4,5)$$

And the total error that was $6$ is reduced to $4$. From here you hopefully can see that the next comparison reaches the ideal. I am not sure if this type of algorithm is needed for your example, as I believe that matching the least number with the largest number, then repeating as I described in the first paragraph, would be all that is needed.

share|improve this answer
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.