Sunday, February 26, 2006

A Quick Problem

I remembered a toy problem I made up while solving a different (less of a toy?) problem and never followed up. Given n positive numbers (possibly fractions) and an integer k, find a way to group the numbers into k groups such that the sum over the groups of the product of numbers in each group is minimized. Does this map to a well-known problem?

5 Comments:

Anonymous D. Eppstein said...

Isn't this just a form of subset sum problem? If k=2, it seems the optimal solution would be to split the numbers so that the sums of the logs of the two subsets are as close to each other as possible.

5:41 PM  
Blogger Suresh said...

I think this generalizes. I'll violently handwave here, but using the equivalence between the (max,+) and (+,X) algebras, what david says should work in general. i.e

take the logs of all elements, and then arrange them as evenly as possible.

idempotence wins again !

8:21 PM  
Blogger metoo said...

Sigh, I do remember thinking of this problem being the bin-packing problem for k=2, but never fully convinced myself. May be that is all it is, even for larger k.

10:35 PM  
Blogger Suresh said...

but it's probably easier than bin packing no ? after all the elements are all poly bounded (since they are logs of the input values)

6:51 AM  
Blogger metoo said...

Suresh: you may have guessed the original context. We have n columns of numbers to compress. We want to group the columns and compress each group rowwise. Say all compression operations use GZIP. What is the best grouping? I was trying to make up toy (ultra toy?) versions of the problem, but gave up.

3:32 AM  

Post a Comment

<< Home