Welcome to the resource topic for 2011/525
Title:
A Note on the Density of the Multiple Subset Sum Problems
Authors: Yanbin Pan, Feng Zhang
Abstract:It is well known that the general subset sum problem is NP-complete. However, almost all subset sum problems with density less than 0.9408\ldots can be solved in polynomial time with an oracle that can find the shortest vector in a special lattice. In this paper, we give a similar result for the multiple subset sum problems which has k subset sum problems with the same solution. Some extended versions of the multiple subset sum problems are also considered. In addition, a modified lattice is involved to make the analysis much simpler than before.
ePrint: https://eprint.iacr.org/2011/525
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .