Our goal is to prove the following 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 factor $r/3$. This, however, does not exclude that simple DP still can efficiently approximate the problem with (larger than $r/3$) factor $r$.

A $k$-Open Problem:Prove a separation between Greedy and simple DP for thesameapproximation factor $r$.

Every family of feasible sets defines the maximization problem: given an assignment of nonnegative weights to the elements of the ground-set, output the maximum total weight of a feasible set. An algorithm approximates such a problem with a factor $r$ iff for every input weighting, its value is at least $1/r$ times the optimal value.

An $(n,m,l)$-Greedy Lemma(Jenkyns [1], Korte-Hausmann [2]): The greedy algorithm has an approximation factor $k$ on a downwards closed family if and only if the family forms a $k$-matroid.

Design Lemma:If $\f$ is an $(n,m,l)$-design for $m\geq 3$ and $l\leq m/3r$, then any (max,+) simple DP algorithm approximating the maximization problem on $\f$ within factor $r$ must have at least $|\f|$ Max and Sum operations.

Our optimization problem is the *Maximum Weight Polynomial* problem.
We fix a prime power $n$, and let our ground-elements be the $n^2$ points of the $n\times n$ grid of pairs of elements of $GF(n)$. Each univariate polynomial over this field defines a set of $n$ points of the grid--the graph of that polynomial. We consider only "low-degree" polynomials, those of degree at most $d-1$, where $d$ is
a parameter. Let $\f$ be the family of all $|\f|=n^{d}$ graphs of low-degree polynomials, and let $\f^*$ be the downward closure of $\f$, where all subsets of
sets in $\f$ are included. Members of $\f^*$ are our
feasible sets.

Claim 1:$\f^*$ is a $k$-matroid for $k=n/d$.

Claim 2:$\f$ is an $(n^2,n,d)$ design.

Now, since the weight of ground-elements are nonnegative, the maximization problems on $\f$ and on $\f^*$ are the same. The Greedy Lemma and Claim 1 imply that the greedy algorithm can approximate this problem with factor $n/d$. But the Design Lemma and Claim 2 imply that every (max,+) simple DP algorithm approximating this problem with factor $n/3d$ must have at least $|\f|=n^{d}$ Max and Sum operations.

- T.A. Jenkyns, The efficacy of the ``greedy'' algorithm, in Proc. of the 7th Southeastern Conf. on Combinatorics, Graph Theory, and Computing, Utilitas Mathematica, Winnipeg (1976) 341-350.
- B. Korte and D. Hausmann, An analysis of the greedy heuristic for independence systems, Annals of Discrete Mathematics, 2 (1978), 65-74. See also a local copy.

S. Jukna, 24.12.2015