Lesson 5

The frontier can also be an algorithmic data structure. Suppose we already know the frontier for the first several stocks. When a new stock arrives, we add each possible number of its shares to each old frontier point, and then prune dominated points again. If the frontier stays small, this may work even when the budget is far too large for a DP table.

This is not magic. In the worst case the frontier can still be huge. But many exact algorithms are useful precisely because they exploit structure in the instance instead of trying to win against every possible input at once.