Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Revision(s):

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

#### Greedy can beat pure dynamic programming

Revision #1
Authors: Stasys Jukna, Hannes Seiwert
Accepted on: 30th May 2018 18:20
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
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.