Search All of the Math Forum:

Views expressed in these public forums are not endorsed by NCTM or The Math Forum.

Notice: We are no longer accepting new posts, but the forums will continue to be readable.

Topic: Seeking an algorithm
Replies: 22   Last Post: Oct 3, 2011 3:01 AM

 Messages: [ Previous | Next ]
 Peter Percival Posts: 2,623 Registered: 10/25/10
Re: Seeking an algorithm
Posted: Sep 29, 2011 4:27 PM

On Thu, 29 Sep 2011 21:13:16 +0100, Helmut Richter <hhr-m@web.de> wrote:

> On Thu, 29 Sep 2011, Peter Percival wrote:
>

>> Given a finite set of numbers, find a partition of it into two sets A
>> and B so
>> that the sum of A's elements is as close to the sum of B's elements as
>> possible. Clearly, one could try all partitions, but if the initial
>> set is
>> large, that might take a long time.
>> "Numbers" might mean real numbers, positive real numbers, integers, or
>> positive integers. Perhaps there are different answers in these four
>> different cases.

>
> Not much difference.
>

>> My first thought for positive numbers of either kind is:
>> (i) Order the numbers according to decreasing size;
>> (ii) put the first in A;
>> (iii) put the second, third, etc, in B until either all numbers are
>> used, or
>> the B sum just exceeds the A sum;
>> (iv) put the next, next after it, etc in A until either all numbers are
>> used,
>> or the A sum just exceeds the B sum;
>> (v) continue thus, stopping when all numbers are used.
>> Is this a good method? "Good" meaning the (or a) most equal partition
>> is
>> always found, and quickly so. I suspect it will sometimes fail to find
>> the
>> most equal partition.

>
> If the numbers are {2, 2, 2, 3, 3}, your algorithm puts the two 3 one
> into
> A and the other into B. There is a different solution which is better.

Thank you. But I would call {2, 2, 2, 3, 3} a multi-set, rather than a
set.

> You can use your algorithm for a bound on the best solution. That is, for
> this example, when your algorithm has a sum of 7 in A and of 5 on B, then
> every other algorithm can be stopped as soon as one set gets a sum of 7
> or
> more. This can save a lot of time when trying when the initial guess is
>
> having exactly or approximately the right difference, so that a solution
> is improved by swapping them. For a practical approximation solution,
> this
> might often suffice. But it will not necessarily find an optimal
> solution,
> to wit when not single numbers have to be swapped but subsets of them --
> thus ending up with more or less the original problem.
>
> The real optimal solution is much more complicated. See for instance
> http://en.wikipedia.org/wiki/Subset_sum_problem .

Thank you for the reference. I had supposed the problem(*) was known, but
did not know its name, so I could not look anything up.

(* I will just remark on how it came to my mind. I was looking at two
piles of books on a table, and I wondered if there was some systematic way
of making two piles so that they were of equal, or near-equal, height, so
that a large book (an atlas, say) could be rested on the top of each pile
and be horizontal, or nearly so. So mine was the positive reals problem.)

--
Using Opera's revolutionary email client: http://www.opera.com/mail/

Date Subject Author
9/29/11 Peter Percival
9/29/11 Karl-Olav Nyberg
9/29/11 Karl-Olav Nyberg
9/29/11 Peter Percival
9/29/11 Karl-Olav Nyberg
9/29/11 Peter Webb
9/29/11 Helmut Richter
9/29/11 Peter Percival
9/29/11 quasi
9/29/11 Helmut Richter
9/29/11 quasi
9/29/11 Helmut Richter
9/29/11 quasi
9/30/11 quasi
10/1/11 Tim Little
10/1/11 quasi
9/29/11 Graham Cooper
9/29/11 Peter Webb
9/30/11 Tim Little
10/1/11 Graham Cooper
10/1/11 Peter Percival
10/3/11 Tim Little
10/3/11 Graham Cooper