Greedy can beat pure dynamic programming

DOI10.1016/J.IPL.2018.10.018zbMATH Open1469.68168arXiv1803.05380OpenAlexW2805855356WikidataQ129012801 ScholiaQ129012801MaRDI QIDQ1628699FDOQ1628699

Authors: Hannes Seiwert, Stasys Jukna 

Publication date: 5 December 2018

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

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.

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

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

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)

Cites Work

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

Cited In (5)

• 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
• Approximation limitations of pure dynamic programming

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)