2020/01/01 by Stasys Jukna, Hannes Seiwert
Computer Science · #Advanced Graph Theory Research #Approximation algorithm #Class (philosophy) #Complexity and Algorithms in Graphs #Converse #Dynamic programming #Electronic circuit #Greedy algorithm #Linear programming #Optimization problem #Polynomial and algebraic computation #Recursion (computer science) #cs.CC
paper · pdf · doi:10.1137/18m1196339
published as SIAM J. on Computing 49:1 (2020) 170-207
openalex publication_date 2020/01/01 · openalex created_date 2020/03/06 · arxiv created 2020/12/23 · arxiv updated 2020/12/24 · openalex updated_date 2026/08/05
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.