16
$\begingroup$

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 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.

Improve this question
$\endgroup$
2
  • 2
    $\begingroup$ Do you mean to define "simple DP algorithm" as "any (max,+) circuit with gates of fan-in 2"? $\endgroup$
    – Joshua Grochow
    Dec 22, 2015 at 1:30
  • $\begingroup$ @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. $\endgroup$
    – Stasys
    Dec 22, 2015 at 10:23

1 Answer 1

Reset to default
8
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ 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. $\endgroup$
    – Sasho Nikolov
    Dec 23, 2015 at 11:44
  • $\begingroup$ @Sasho: Yes, these are indeed cute DP based algorithms. Woeginger 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. $\endgroup$
    – Stasys
    Dec 23, 2015 at 16:37
  • $\begingroup$ 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. $\endgroup$
    – Sasho Nikolov
    Dec 23, 2015 at 21:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.