\( \newcommand{\CC}{\mathbf{C}} \newcommand{\F}{\mathcal{F}} \newcommand{\f}{\mathcal{F}} \newcommand{\rnw}{\mathbf{w}} \newcommand{\RR}{\mathbb{R}} \newcommand{\NN}{\mathbb{N}} \def\tikim{\mathrm{Pr}} \def\prob#1{\tikim\big[#1\big]} \newcommand{\Min}[2]{\mathrm{min}_{#2}(#1)} \newcommand{\Max}[2]{\mathrm{max}_{#2}(#1)} \DeclareDocumentCommand\setdef{mo}{\left\{#1\IfNoValueTF{#2}{}{ : #2}\right\}} \)

Separating Greedy and "simple" DP

This is a partial answer to my Question 2 raised here

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

Open Problem: Prove a separation between Greedy and simple DP for the same approximation factor $r$.
A $k$-matroid is a downwards closed family $\f$ of sets (called feasible sets) with the property that there are no two feasible sets $S$ and $T$ such that both are maximal feasible subsets of $S\cup T$, but $|T|>k\cdot|S|$. Being maximal feasible means that neither of them can be extended to a larger feasible set by adding some element from another set. Thus, matroids are exactly $1$-matroids. It is known that an intersection of $k$ matroids is a $k$-matroid.

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.

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.
An $(n,m,l)$-design is a family of subsets of an $n$-element set such that every set has at last $m$ elements, no two sets share $l$ or more elements.
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.
Proof: See here . $\Box$

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$.
Proof: Assume contrariwise that $\f^*$ is not a $k$-matroid. Then there must be two feasible sets $S$ and $T$ such that both are maximal feasible subsets of $S\cup T$, but $|T| > k\cdot|S|$. Both sets $S$ and $T$ are subsets of graphs of some low-degree polynomials $s(x)$ and $t(x)$. So, $S=\{(i,s(i))\colon i\in I\}$ for some set $I$ of $|I|=|S| < |T|/k\leq n/k=d$ field elements. Since $|T|$ is strictly larger than $|S|=|I|$, there must be a field element $j\not\in I$ such that the point $(j,t(j))$ belongs to $T$. Since the extended set $S\cup\{(j,t(j))\}$ has only $|S|+1\leq d$ elements, and low-degree polynomials can have degree up to $d-1$, this extended set is also a subset of the graph of some low-degree polynomial, and hence, is a feasible set. This contradicts the maximality of $S$. $\Box$

Claim 2: $\f$ is an $(n^2,n,d)$ design.
Proof: Each graph of a polynomial has exactly $n$ points, and no two of them can share $d$ or more points in common, since their degrees are at most $d-1$. $\Box$

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.

References:

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