I am looking for algorithmic techniques to solve the Subset Sum Problem in pseudopolynomial time. There is, of course, a textbook dynamic programming approach for Subset Sum. Have any other algorithmic techniques (Randomized, Linear Programming...) been successfully applied to this problem?
In [1], the authors state that "[T]the only algorithm known to solve subset sum (in time polynomial in the numbers involved) is dynamic programming" (page 3). This paper, however, is 8 years old and it might be possible that some progress has been made in the recent past.
[1] Reid Andersen, and Uriel Feige. Interchanging distance and capacity in probabilistic mappings. Available at https://arxiv.org/abs/0907.3631v1
-
1$\begingroup$ cseweb.ucsd.edu/~dakane/subsetsum.pdf $\endgroup$user12859– user128592017年10月10日 09:52:29 +00:00Commented Oct 10, 2017 at 9:52
-
2$\begingroup$ @RickyDemer Perhaps you would like to convert this to a full-fledged answer? $\endgroup$Yuval Filmus– Yuval Filmus2017年10月10日 10:33:10 +00:00Commented Oct 10, 2017 at 10:33
1 Answer 1
Yes.
This paper has applied polynomial arithmetic to that problem.
Explore related questions
See similar questions with these tags.