Approximation limitations of pure dynamic programming

DOI10.1137/18M1196339MaRDI QIDQ5216795zbMATH OpenOpenAlexFDO

Authors Hannes Seiwert, Stasys Jukna

Publication date 20 February 2020

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

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

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)

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.

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

Cites work

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

Cited in

(10)

• Lower bounds for tropical circuits and dynamic programs
• 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

Describes a project that uses

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)