ECCC-Report TR19-158https://eccc.weizmann.ac.il/report/2019/158Comments and Revisions published for TR19-158en-usMon, 11 Nov 2019 20:19:07 +0200
Paper TR19-158
| Sorting Can Exponentially Speed Up Pure Dynamic Programming |
Stasys Jukna,
Hannes Seiwert
https://eccc.weizmann.ac.il/report/2019/158Many 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.Mon, 11 Nov 2019 20:19:07 +0200https://eccc.weizmann.ac.il/report/2019/158