Project: Portfolio Selection · Tracking Dynamic Programming

Lesson 4

Nikolai Chukhin · Alexander S. Kulikov

This limitation is not an accident of our recurrence. Even the much simpler question “can some subset of numbers have total sum exactly \(T\)?” is the subset sum problem. Its generating function is \[\prod_{i}(1+z^{s_i}),\] and the question asks whether the coefficient of \(z^{T}\) is nonzero. This is the same kind of object that appears in our portfolio polynomial.

For the curious 🤓

It is worth pausing on how far the subset sum problem has been pushed, because the two algorithms in this project are exactly its two classical lines of attack.

The dynamic-programming table is the pseudo-polynomial side. For a target \(T\), the textbook bound is \(O(nT)\), and it was eventually improved all the way to a randomized, essentially linear \(\widetilde{O}(n+T)\) algorithm (Bringmann, 2017). This is essentially optimal: under the Strong Exponential Time Hypothesis, no algorithm runs in time \(T^{1-\varepsilon}\ 2^{o(n)}\).

Meet in the middle is the exponential side. Its \(O^{*}(2^{n/2})\) running time goes back to Horowitz and Sahni in 1974, and, remarkably, no one knows how to do substantially better in the worst case: whether subset sum admits an \(O^{*}\!\left(2^{(1/2-\varepsilon)n}\right)\) algorithm is a long-standing open problem.