Greedy can beat pure dynamic programming

DOI10.1016/J.IPL.2018.10.018MaRDI QIDQ1628699zbMATH OpenOpenAlexWikidataFDO

Authors Hannes Seiwert, Stasys Jukna

Publication date 5 December 2018

Published in Information Processing Letters (Search for Journal in Brave)

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

zbMATH Keywords

computational complexityspanning treearithmetic circuittropical circuit

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Analysis of algorithms (68W40) Dynamic programming (90C39) Boolean programming (90C09)

Abstract: Many dynamic programming algorithms for discrete 0-1 optimizationproblems are "pure" in that their recursion equations only use min/max and addition operations, and do not depend on actual input weights. The well-known greedy algorithm of Kruskal solves the minimum weight spanning tree problem on $n$-vertex graphs using only $O(n^{2}logn)$ operations. We prove that any pure DP algorithm for this problem must perform $2^{Omega(sqrtn)}$ operations. Since the greedy algorithm can also badly fail on some optimization problems, easily solvable by pure DP algorithms, our result shows that the computational powers of these two types of algorithms are incomparable.

Recommendations

• Sorting can exponentially speed up pure dynamic programming
• Canonical greedy algorithms and dynamic programming
• Approximation limitations of pure dynamic programming
• A stronger model of dynamic programming algorithms
• Greedy Families for Linear Objective Functions

Cites work

• scientific article; zbMATH DE number 3384060 (Why is no real title available?)
• A Dynamic Programming Approach to Sequencing Problems
• A Theorem on Boolean Matrices
• Finding optimum branchings
• Lower bounds for tropical circuits and dynamic programs
• Negation can be exponentially powerful
• On a routing problem
• On the Parallel Evaluation of Multivariate Polynomials
• On the shortest spanning subtree of a graph and the traveling salesman problem
• Optimum branchings
• Probability Inequalities for Sums of Bounded Random Variables
• Random graphs.
• Some Exact Complexity Results for Straight-Line Computations over Semirings
• The steiner problem in graphs
• The tail of the hypergeometric distribution

Cited in

(5)

• Approximation limitations of pure dynamic programming
• Canonical greedy algorithms and dynamic programming
• ReLU neural networks of polynomial size for exact maximum flow computation
• Sorting can exponentially speed up pure dynamic programming
• Beating a Benchmark: Dynamic Programming May Not Be the Right Numerical Approach

Describes a project that uses

Uses Software

• Algorithm 97

This page was built for publication: Greedy can beat pure dynamic programming

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