1
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ cseweb.ucsd.edu/~dakane/subsetsum.pdf ​ ​ $\endgroup$ – user12859 Oct 10 '17 at 9:52
  • 2
    $\begingroup$ @RickyDemer Perhaps you would like to convert this to a full-fledged answer? $\endgroup$ – Yuval Filmus Oct 10 '17 at 10:33
1
$\begingroup$

Yes.

This paper has applied polynomial arithmetic to that problem.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.