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?
posted by metoo at 4:37 PM
5 Comments:
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.
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 !
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.
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)
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.
Post a Comment
<< Home