Risolvere la somma del sottoinsieme senza l'uso della programmazione dinamica

Question

Sto cercando tecniche algoritmiche per risolvere il problema della somma del sottoinsieme nel tempo pseudopolinomiale. Esiste, ovviamente, un approccio di programmazione dinamica del libro di testo per la somma del sottoinsieme. Qualche altra tecnica algoritmica (programmazione randomizzata, lineare ...) è stata applicata con successo a questo problema?

In [1], gli autori affermano che [t] l'unico algoritmo noto per risolvere la somma del sottoinsieme (nel tempo polinomiale nei numeri coinvolti) è la programmazione dinamica" (pagina 3). Questo documento, tuttavia, ha 8 anni e potrebbe essere possibile che alcuni progressi siano stati compiuti nel recente passato.

1] Reid Andersen e Uriel Feige. Distanza e capacità di scambiatura nelle mappature probabilistiche. Disponibile a https://arxiv.org/abs/0907.3631v1