Approximation limitations of pure dynamic programming

DOI10.1137/18M1196339zbMATH Open1441.90174arXiv2012.12831OpenAlexW3113954267MaRDI QIDQ5216795FDOQ5216795

Authors: Hannes Seiwert, Stasys Jukna 

Publication date: 20 February 2020

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Abstract: 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.

Full work available at URL: https://arxiv.org/abs/2012.12831

Recommendations

• Lower bounds for tropical circuits and dynamic programs
• Tropical complexity, Sidon sets, and dynamic programming
• Greedy can beat pure dynamic programming
• Limitations of incremental dynamic programming
• Sorting can exponentially speed up pure dynamic programming

zbMATH Keywords

dynamic programminggreedy algorithmlower boundsapproximation

Mathematics Subject Classification ID

Dynamic programming (90C39) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Tropical optimization (e.g., max-plus optimization) (90C24)

Cites Work

• Title not available (Why is that?)
• Error bounds for convolutional codes and an asymptotically optimum decoding algorithm
• On a routing problem
• Title not available (Why is that?)
• A Dynamic Programming Approach to Sequencing Problems
• A Theorem on Boolean Matrices
• Title not available (Why is that?)
• A THEOREM ON INDEPENDENCE RELATIONS
• Some Exact Complexity Results for Straight-Line Computations over Semirings
• The monotone circuit complexity of Boolean functions
• Matroids and the greedy algorithm
• The asymptotic number of geometries
• On the number of matroids
• Lower bounds for constant weight codes
• A method for deriving lower bounds for the complexity of monotone arithmetic circuits computing real polynomials
• On the Number of Combinatorial Geometries
• The steiner problem in graphs
• Title not available (Why is that?)
• Lower bounds on monotone complexity of the logical permanent
• Title not available (Why is that?)
• Subtraction-free complexity, cluster transformations, and spanning trees
• Determination of two vectors from the sum
• Greedy can beat pure dynamic programming
• Title not available (Why is that?)
• Tropical complexity, Sidon sets, and dynamic programming

Cited In (9)

• Tropical Circuit Complexity
• Coin flipping in dynamic programming is almost useless
• Exponential lower bounds on the complexity of a class of dynamic programs for combinatorial optimization problems
• General limit value in dynamic programming
• Notes on Boolean read-\(k\) and multilinear circuits
• Sorting can exponentially speed up pure dynamic programming
• Beating a Benchmark: Dynamic Programming May Not Be the Right Numerical Approach
• Greedy can beat pure dynamic programming
• Tropical complexity, Sidon sets, and dynamic programming

Uses Software

• Algorithm 97

This page was built for publication: Approximation limitations of pure dynamic programming

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5216795)