Approximation Limitations of Pure Dynamic Programming

DOI10.1137/18M1196339zbMath1441.90174arXiv2012.12831OpenAlexW3113954267MaRDI QIDQ5216795

Hannes Seiwert, Stasys P. 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 programmingapproximationgreedy algorithmlower bounds

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)

Uses Software

• Algorithm 97

Cites Work

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

This page was built for publication: Approximation Limitations of Pure Dynamic Programming