TR19-158 Authors: Stasys Jukna, Hannes Seiwert

Publication: 11th November 2019 20:19

Downloads: 578

Keywords:

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.