Sorting can exponentially speed up pure dynamic programming

DOI10.1016/J.IPL.2020.105962MaRDI QIDQ783692zbMATH OpenOpenAlexFDO

Authors Hannes Seiwert, Stasys Jukna

Publication date 4 August 2020

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

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

zbMATH Keywords

computational complexitydynamic programmingspanning treeMST problem

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Analysis of algorithms (68W40) Dynamic programming (90C39) Searching and sorting (68P10)

Abstract: Many discrete minimization problems, including various versions of the shortest path problem, can be efficiently solved by dynamic programming (DP) algorithms that are "pure" in that they only perform basic operations, as min, max, +, but no conditional branchings via if-then-else in their recursion equations. It is known that any pure (min,+) DP algorithm solving the minimum weight spanning tree problem on undirected n-vertex graphs must perform at least $2^{Omega(sqrtn)}$ operations. We show that this problem can be solved by a pure (min,max,+) DP algorithm performing only $O(n^3)$ operations. The algorithm is essentially a (min,max) algorithm: addition operations are only used to output the final values. The presence of both min and max operations means that now DP algorithms can sort: this explains the title of the paper.

Recommendations

• Greedy can beat pure dynamic programming
• Approximation limitations of pure dynamic programming
• Online Dynamic Programming Speedups
• scientific article; zbMATH DE number 3978860
• A stronger model of dynamic programming algorithms

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
• A note on practical construction of maximum bandwidth paths.
• Error bounds for convolutional codes and an asymptotically optimum decoding algorithm
• Greedy can beat pure dynamic programming
• On a routing problem
• Some Exact Complexity Results for Straight-Line Computations over Semirings
• Subtraction-free complexity, cluster transformations, and spanning trees
• The steiner problem in graphs

Cited in

(3)

• Approximation limitations of pure dynamic programming
• scientific article; zbMATH DE number 4110087 (Why is no real title available?)
• Greedy can beat pure dynamic programming

Describes a project that uses

Uses Software

• Algorithm 97

This page was built for publication: Sorting can exponentially speed up pure dynamic programming

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