2 edited tags
| link
source | link

Solving Subset Sum Without the Use of Dynamic Programming

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