  We prove the first, even super-polynomial, 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 also the converse holds.
