Approximation Limitations of Pure Dynamic Programming
Stasys P. Jukna, Hannes Seiwert · SIAM Journal on Computing · 2020
We prove the first, even superpolynomial, lower bounds on the size of tropical (min,+) and (max,+) circuits approximating given optimization problems. Many classical dynamic programming (DP) algorithms for optimization problems are pure in that they only use the basic $\min$, $\max$, $+$ operations in their recursion equations. Tropical circuits constitute a rigorous mathematical model for this class of algorithms. An algorithmic consequence of our lower bounds for tropical circuits is that the approximation powers of pure DP algorithms and greedy algorithms are incomparable. That pure DP algorithms can hardly beat greedy in approximation is long known. New in this consequence is that the converse also holds.