<p>I think the answer to my Question 1 is <em>affirmative</em>: there <em>are</em> matroids on which simple DP fails badly! That is, simple DP may be much worse than Greedy when trying to solve an optimization problem <em>exactly</em>.</p>
<p>Let the ground set consists of all edges of <span class="math-container">$K_n$</span>. As our family of feasible solutions take the family of all forests in <span class="math-container">$K_n$</span>. This is a motroid, and its bases are spanning trees. So, the corresponding to this matroid polynomial is a multilinear polynomial <span class="math-container">$f$</span> whose monomials correspond to spanning trees. <a href="http://dl.acm.org/citation.cfm?doid=322326.322341" rel="nofollow noreferrer">Jerrum and Snir</a> have proved (in Section 4.5) that <span class="math-container">$f$</span> requires monotone arithmetic circuits of exponential size. This already implies that every <span class="math-container">$(\max,+)$</span> circuit, and hence, also every simple DP algorithm, must use an exponential number of Max and Sum operations to solve the maximum weight spanning tree problem.</p>
<p>As Igor Sergeev told me, an affirmative answer to Question 1 follows also by counting: <a href="http://www.sciencedirect.com/science/article/pii/0097316574900636" rel="nofollow noreferrer">Knuth</a> has shown that there <span class="math-container">$2^{2^n/n^{3/2}}$</span> matroids on <span class="math-container">$n$</span> points.</p>
<p>P.S. I will not &quot;accept&quot; this my half-answer (which came only right now after rethinking the connection with  monotone arithmetic circuits), because a much more interesting Question 2 remains open: how much worse simple DP can be than Greedy when <b>approximating</b> optimization problems? This question is more interesting, because Greedy has often a fairly good approximation factor. This factor is known to coincide(!) with the so-called &quot;rank quotient&quot; of the underlying family of feasible solutions (see, e.g. <a href="https://web.vu.lt/mif/s.jukna/EC_Book_2nd/comment3.html" rel="nofollow noreferrer">this writeup</a>. In the case of Max-Weight Matching problem, this quotient is <span class="math-container">$2$</span>, and is at most <span class="math-container">$k$</span> for any intersection of <span class="math-container">$k$</span> matroids. On the other hand, as far as I know, DP based approximation algorithms usually use some kind of &quot;scaling&quot; of input weights, and only apply to &quot;knapsack like&quot; problems or some scheduling problems. A negative answer to Question 2 would <em>confirm</em> this seeming &quot;approximation weakness&quot; of DP.</p>

CC BY-SA 3.0
2015-12-23T11:44:50.663Z
A somewhat tangential remark: DP is also used in the Arora-style algorithms for various fixed dimension Euclidean problems, e.g. Euclidean TSP. But this is still in the spirit of rounding the input.
Sasho Nikolov
CC BY-SA 3.0
2015-12-23T16:37:04.960Z
@Sasho: Yes, these are indeed cute DP based algorithms.
[Woeginger](http://pubsonline.informs.org/doi/abs/10.1287/ijoc.12.1.57.11901) has even made an attempt to capture  problems for which DP can help to approximate them. But I haven't seen any good DP approximation which is *pure* (only Max and Sum or Min and Sum, no rounding/scaling, no ArgMax etc.)  Of course, this could be just my fault: approximation algorithms is something new for me.
Stasys
CC BY-SA 3.0
2015-12-23T21:41:22.307Z
I am not aware of any example of a good "pure" DP approximation, in your sense of pure: all examples I am aware of use some form of rounding.
Sasho Nikolov
CC BY-SA 4.0
2015-12-22T15:54:33.730Z
2023-12-18T12:52:18.743Z
2023-12-18T12:52:18.743Z
Stasys
<p>In the circuit complexity, we have separations between powers of various circuit models.</p>
<p>
In the proof complexity, we have separations between  powers of various proof systems.
<p>
But in the algorithmic, we still have only few separations between powers of <b>algorithmic paradigms</b>. <p>
My questions below aim to touch this latter problem for two paradigms: Greedy and Dynamic Programming. 
<p>
<p>We have a ground set of elements, and some family of its subsets declared as feasible solutions. We assume that this family is downwards closed: subsets of feasible solution are feasible. Given an assignment of nonnegative weights to the ground-elements, the problem   is to compute the maximum total weight  of a feasible solution.</p>
<p>
The greedy algorithm starts with an empty partial solution, and at each step, 
it adds a a yet-not-treated element of largest weight iff this is possible, i.e. if 
the extended solution is still feasible. The well-known Rado-Edmonds theorem states  that this algorithm will find an optimal solution for all input weightings iff the family of feasible solutions  is a matroid.
<p>
Roughly speaking, a DP algorithm is <i>simple</i>, if it only uses Max and Sum (or Min and Sum) operations. To be more specific (as suggested by Joshua), by a <i>simple DP</i> algorithm I will mean a (max,+) circuit with fanin-2 Max and Sum gates. Inputs are variables, the <span class="math-container">$i$</span>-th of which correspond to the weight given to the <span class="math-container">$i$</span>-th element. Such a circuit can solve <i>any</i> such problem by just computing the maximum total weight of a feasible solution. But this can be a huge overdone, if we have exponentially many such solutions (as is almost always the case).
<blockquote><b> Question 1:</b>
 Are there matroids, on which any simple DP algorithm will need a super-polynomial number of operations to solve the corresponding maximization problem?
</blockquote>
COMMENT (added 24.12.2015): This question is already answered (see below): there <b>are</b> such matroids, even in overwhelming majority.
<p>
<p>The next question asks to separate Greedy and simple DP for <b>approximation</b> problems. In the <i>Max-Weight Matching</i> problem, the family of feasible solutions consists of all matchings in the complete bipartite <span class="math-container">$n\times n$</span> graph. For a given assignment of weights to its edges, the goal is to compute the maximum weight of a matching (this will always be a perfect matching, since weight are nonnegative).</p>
<p>
The simple greedy algorithm can approximate this problem within the  factor 2: just always take a not-yet-seen disjoint edge of maximal weight. The obtained weight will be at least half of optimal weight.
<blockquote><b> Question 2:</b>
Can a simple DP algorithm approximate the Max-Weight Matching problem within the factor 2 by using only polynomially many Max and Sum operations?
</blockquote>
Of course, a trivial DP algorithm, which outputs <span class="math-container">$n$</span> times the maximum weight of an edge, approximates this problem within the factor <span class="math-container">$n$</span>. But we want a much smaller factor. I guess that even a factor <span class="math-container">$n/\log n$</span> cannot be achieved but, again: how to <b>prove</b> this?
<p>
RELATED: A cousin of the Max-Weight Matching is the <i>Assignment problem</i>: find the <i>minimum</i> weight of a perfect matching. This problem can be solved (even exactly) by linear programming (so-called Hungarian algorithm) by using only <span class="math-container">$O(n^3)$</span> operations. But the lower bound of Razborov on the size of monotone boolean circuits computing the permanent function implies (not quite directly) that any (min,+) circuit approximating this problem within any(!) finite factor must use <span class="math-container">$n^{\Omega(\log n)}$</span> operations. Thus, for <i>minimization</i> problems, simple DP algorithms may be much weaker than Linear Programming. My questions above aim to show that such DP algorithms may be even weaker than Greedy.
<p>
Have somebody seen similar questions being considered by someone? 
<hr>
ADDED (on 24.12.2015): Question 2 aims to show that <b>one particular</b> maximization problem (the Max-Weight Matching problem), which  can be approximated by the greedy algorithm with factor <span class="math-container">$r=2$</span>, cannot be approximated by a poly-size simple DP with the <b>same</b> factor <span class="math-container">$r$</span>. Meanwhile, I obtained a weaker separation between Greedy and simple DP: for every <span class="math-container">$r=o(n/\log n)$</span>, there is an explicit maximization problem which can be approximated by the greedy algorithm with factor <span class="math-container">$r$</span>,
but no poly-size simple DP algorithm can approximate this problem with a <b>smaller</b> factor <span class="math-container">$&lt; r/3$</span> (see <a href="https://web.vu.lt/mif/s.jukna/greedy1.html" rel="nofollow noreferrer"> here</a> for a sketch). Still, Question 2 itself (not necessarily for this particular Max-Weight problem) remains actual: it would be interesting to target the <b>same</b> factor by both algorithms.

CC BY-SA 3.0
2015-12-22T01:30:54.293Z
Do you mean to *define* "simple DP algorithm" as "any (max,+) circuit with gates of fan-in 2"?
Joshua Grochow
CC BY-SA 3.0
2015-12-22T10:23:33.107Z
@Joshua: yes. Say, Bellman-Ford for shortest s-t path has an input variable $x_{i,j}$ for each edge of $K_n$. The gates on the 1-st layer are $D(j,1) = x_{s,j}$. On the l-th layer, we have $D(j,l) = \min\{ D(j,l-1), min_i\{D(i,l-1)+x_{i,j}\}\}$. The output gate is $D(t,n-1)$. There are $O(n^3)$ gates in total. Actually, restitction on faninis not so important in my question.
Stasys
<cc.complexity-theory><circuit-complexity><lower-bounds><dynamic-programming>
Is Dynamic Programming never weaker than Greedy?
Stasys
# Is Dynamic Programming never weaker than Greedy?

(Asked by: username_0 on 2015-12-21)

In the circuit complexity, we have separations between powers of various circuit models.

In the proof complexity, we have separations between powers of various proof systems.

But in the algorithmic, we still have only few separations between powers of **algorithmic paradigms**.

My questions below aim to touch this latter problem for two paradigms: Greedy and Dynamic Programming.

We have a ground set of elements, and some family of its subsets declared as feasible solutions. We assume that this family is downwards closed: subsets of feasible solution are feasible. Given an assignment of nonnegative weights to the ground-elements, the problem is to compute the maximum total weight of a feasible solution.

The greedy algorithm starts with an empty partial solution, and at each step,
it adds a a yet-not-treated element of largest weight iff this is possible, i.e. if
the extended solution is still feasible. The well-known Rado-Edmonds theorem states that this algorithm will find an optimal solution for all input weightings iff the family of feasible solutions is a matroid.

Roughly speaking, a DP algorithm is *simple*, if it only uses Max and Sum (or Min and Sum) operations. To be more specific (as suggested by Joshua), by a *simple DP* algorithm I will mean a (max,+) circuit with fanin-2 Max and Sum gates. Inputs are variables, the $i$-th of which correspond to the weight given to the $i$-th element. Such a circuit can solve *any* such problem by just computing the maximum total weight of a feasible solution. But this can be a huge overdone, if we have exponentially many such solutions (as is almost always the case).
> **Question 1:**
> Are there matroids, on which any simple DP algorithm will need a super-polynomial number of operations to solve the corresponding maximization problem?

COMMENT (added 24.12.2015): This question is already answered (see below): there **are** such matroids, even in overwhelming majority.

The next question asks to separate Greedy and simple DP for **approximation** problems. In the *Max-Weight Matching* problem, the family of feasible solutions consists of all matchings in the complete bipartite $n\times n$ graph. For a given assignment of weights to its edges, the goal is to compute the maximum weight of a matching (this will always be a perfect matching, since weight are nonnegative).

The simple greedy algorithm can approximate this problem within the factor 2: just always take a not-yet-seen disjoint edge of maximal weight. The obtained weight will be at least half of optimal weight.
> **Question 2:**
> Can a simple DP algorithm approximate the Max-Weight Matching problem within the factor 2 by using only polynomially many Max and Sum operations?

Of course, a trivial DP algorithm, which outputs $n$ times the maximum weight of an edge, approximates this problem within the factor $n$. But we want a much smaller factor. I guess that even a factor $n/\log n$ cannot be achieved but, again: how to **prove** this?

RELATED: A cousin of the Max-Weight Matching is the *Assignment problem*: find the *minimum* weight of a perfect matching. This problem can be solved (even exactly) by linear programming (so-called Hungarian algorithm) by using only $O(n^3)$ operations. But the lower bound of Razborov on the size of monotone boolean circuits computing the permanent function implies (not quite directly) that any (min,+) circuit approximating this problem within any(!) finite factor must use $n^{\Omega(\log n)}$ operations. Thus, for *minimization* problems, simple DP algorithms may be much weaker than Linear Programming. My questions above aim to show that such DP algorithms may be even weaker than Greedy.

Have somebody seen similar questions being considered by someone?

---

ADDED (on 24.12.2015): Question 2 aims to show that **one particular** maximization problem (the Max-Weight Matching problem), which can be approximated by the greedy algorithm with factor $r=2$, cannot be approximated by a poly-size simple DP with the **same** factor $r$. Meanwhile, I obtained a weaker separation between Greedy and simple DP: for every $r=o(n/\log n)$, there is an explicit maximization problem which can be approximated by the greedy algorithm with factor $r$,
but no poly-size simple DP algorithm can approximate this problem with a **smaller** factor $< r/3$ (see  [here](https://web.vu.lt/mif/s.jukna/greedy1.html) for a sketch). Still, Question 2 itself (not necessarily for this particular Max-Weight problem) remains actual: it would be interesting to target the **same** factor by both algorithms.

**Tags:** cc.complexity-theory, circuit-complexity, lower-bounds, dynamic-programming
> **Comments:**
> **username_1**: Do you mean to *define* "simple DP algorithm" as "any (max,+) circuit with gates of fan-in 2"?  
> **username_0**: @Joshua: yes. Say, Bellman-Ford for shortest s-t path has an input variable $x_{i,j}$ for each edge of $K_n$. The gates on the 1-st layer are $D(j,1) = x_{s,j}$. On the l-th layer, we have $D(j,l) = \min\{ D(j,l-1), min_i\{D(i,l-1)+x_{i,j}\}\}$. The output gate is $D(t,n-1)$. There are $O(n^3)$ gates in total. Actually, restitction on faninis not so important in my question.  

---

## 1 answers

### Answer by username_0 on 2015-12-22. Score: 8

I think the answer to my Question 1 is *affirmative*: there *are* matroids on which simple DP fails badly! That is, simple DP may be much worse than Greedy when trying to solve an optimization problem *exactly*.

Let the ground set consists of all edges of $K\_n$. As our family of feasible solutions take the family of all forests in $K\_n$. This is a motroid, and its bases are spanning trees. So, the corresponding to this matroid polynomial is a multilinear polynomial $f$ whose monomials correspond to spanning trees. [Jerrum and Snir](http://dl.acm.org/citation.cfm?doid=322326.322341) have proved (in Section 4.5) that $f$ requires monotone arithmetic circuits of exponential size. This already implies that every $(\max,+)$ circuit, and hence, also every simple DP algorithm, must use an exponential number of Max and Sum operations to solve the maximum weight spanning tree problem.

As Igor Sergeev told me, an affirmative answer to Question 1 follows also by counting: [Knuth](http://www.sciencedirect.com/science/article/pii/0097316574900636) has shown that there $2^{2^n/n^{3/2}}$ matroids on $n$ points.

P.S. I will not "accept" this my half-answer (which came only right now after rethinking the connection with monotone arithmetic circuits), because a much more interesting Question 2 remains open: how much worse simple DP can be than Greedy when **approximating** optimization problems? This question is more interesting, because Greedy has often a fairly good approximation factor. This factor is known to coincide(!) with the so-called "rank quotient" of the underlying family of feasible solutions (see, e.g. [this writeup](https://web.vu.lt/mif/s.jukna/EC_Book_2nd/comment3.html). In the case of Max-Weight Matching problem, this quotient is $2$, and is at most $k$ for any intersection of $k$ matroids. On the other hand, as far as I know, DP based approximation algorithms usually use some kind of "scaling" of input weights, and only apply to "knapsack like" problems or some scheduling problems. A negative answer to Question 2 would *confirm* this seeming "approximation weakness" of DP.

> **Comments:**
> **username_2**: A somewhat tangential remark: DP is also used in the Arora-style algorithms for various fixed dimension Euclidean problems, e.g. Euclidean TSP. But this is still in the spirit of rounding the input.  
> **username_0**: @Sasho: Yes, these are indeed cute DP based algorithms. [Woeginger](http://pubsonline.informs.org/doi/abs/10.1287/ijoc.12.1.57.11901) has even made an attempt to capture  problems for which DP can help to approximate them. But I haven't seen any good DP approximation which is *pure* (only Max and Sum or Min and Sum, no rounding/scaling, no ArgMax etc.)  Of course, this could be just my fault: approximation algorithms is something new for me.  
> **username_2**: I am not aware of any example of a good "pure" DP approximation, in your sense of pure: all examples I am aware of use some form of rounding.  

---

