I have a sorted multiset (size < 100, real valued) and want to determine the $n^{\mathrm{th}}$ largest of all possible subset sums (including multiplicity in the sums).

Attempt at solving :

I have been looking at ordering the sums starting with the unbounded knapsack problem (UKP) with equal weights to find the sets of each size with minimal sum, then establishing a rule for determining the order of corresponding sets after replacing elements, in the hope that this would reduce the number of comparisons. However, this doesn't seem to simplify the problem.

  • $\begingroup$ math.stackexchange.com/questions/89419/… $\endgroup$ – Yuval Filmus Dec 7 '20 at 22:03
  • $\begingroup$ Thank you for that reference. It does accomplish what I'm looking for, but I can't reach large values in the search space with that speed. Is there any chance I could skip over a chunk of subsets without explicitly finding and summing them? $\endgroup$ – dripset_pushbert Dec 7 '20 at 22:21
  • 1
    $\begingroup$ The problem is NP-hard: if we could solve your problem efficiently, it would be easy to solve the subset sum problem too (using binary search). I don't know whether there is a way to take advantage of the known algorithms for subset sum to solve this for the a multiset of size 100; I haven't figured out a way, but maybe someone else will have some ideas. $\endgroup$ – D.W. Dec 8 '20 at 0:00
  • $\begingroup$ I see, you have clarified the relation between my problem and subset sum and a lower bound on time complexity is already very good to know, thank you. $\endgroup$ – dripset_pushbert Dec 8 '20 at 0:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.