Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR19-158 | 11th November 2019 18:27

Sorting Can Exponentially Speed Up Pure Dynamic Programming


Authors: Stasys Jukna, Hannes Seiwert
Publication: 11th November 2019 20:19
Downloads: 647


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(\sqrt{n})}$ operations. We show that this problem \emph{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.

ISSN 1433-8092 | Imprint