Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR18-049 | 30th May 2018 18:20

Greedy can beat pure dynamic programming

RSS-Feed




Revision #1
Authors: Stasys Jukna, Hannes Seiwert
Accepted on: 30th May 2018 18:20
Downloads: 71
Keywords: 


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\log n)$ operations. We prove that any pure DP algorithm for this problem must perform $2^{\Omega(\sqrt{n})}$ 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.



Changes to previous version:

The first structural claim of the Forest lemma (that the sets of vertices in the connected components of all forests from one side must be the same) in the previous version is just wrong. We now use entirely different arguments to prove a slightly weaker version of the numerical claim of the Forest lemma. The resulting lower bound is weaker, but still exponential.


Paper:

TR18-049 | 14th March 2018 19:21

Greedy can also beat pure dynamic programming





TR18-049
Authors: Stasys Jukna, Hannes Seiwert
Publication: 14th March 2018 19:21
Downloads: 380
Keywords: 


Abstract:

Many dynamic programming algorithms are ``pure'' in that they only use min or max and addition operations in their recursion equations. The well known greedy algorithm of Kruskal solves the minimum weight spanning tree problem on $n$-vertex graphs using only $O(n^2\log n)$ operations. We prove that any pure DP algorithm for this problem must perform $2^{\Omega(n)}$ 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.



ISSN 1433-8092 | Imprint