Abstract
We develop general lower bound arguments for approximating topical (min,+) and (max,+) circuits, and use them to prove the first non-trivial, even super-polynomial, lower bounds on the size of such circuits approximating some explicit optimization problems. In particular, these bounds show that the approximation powers of pure dynamic programming algorithms and greedy algorithms are incomparable.