Drexel dragonThe Math ForumDonate to the Math Forum

Search All of the Math Forum:

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

Math Forum » Discussions » sci.math.* » sci.math

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

Advanced Search

Back to Topic List Back to Topic List Jump to Tree View Jump to Tree View   Messages: [ Previous | Next ]
Peter Percival

Posts: 1,387
Registered: 10/25/10
Re: Seeking an algorithm
Posted: Sep 29, 2011 4:27 PM
  Click to see the message monospaced in plain text Plain Text   Click to reply to this topic Reply

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

> 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
> already good.
> You can also start with your algorithm and then find pairs of numbers
> 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/

Point your RSS reader here for a feed of the latest messages in this topic.

[Privacy Policy] [Terms of Use]

© The Math Forum 1994-2015. All Rights Reserved.