Résolution d'une somme sous-ensemble sans l'utilisation de la programmation dynamique

Question

Je recherche des techniques algorithmiques pour résoudre le problème de somme sous-ensemble en temps pseudopolynomial. Il existe, bien sûr, une approche de programmation dynamique du manuel pour la somme des sous-ensembles. Les autres techniques algorithmiques (programmation linéaire randomisée ...) ont-elles été appliquées avec succès à ce problème?

Dans [1], les auteurs indiquent que [t] le seul algorithme connu pour résoudre la somme du sous-ensemble (dans le polynôme du temps dans les nombres impliqués) est la programmation dynamique" (page 3). Cet article, cependant, a 8 ans et il est possible que certains progrès aient été réalisés dans le passé récent.

1] Reid Andersen et Uriel Feige. Échange de distance et capacité dans les mappages probabilistes. Disponible à https://arxiv.org/abs/0907.3631v1