## 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 , Korte-Hausmann ): 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
{"ft_lang_label":"__label__en","ft_lang_prob":0.89877266,"math_prob":0.99973863,"size":4017,"snap":"2020-45-2020-50","text_gpt3_token_len":1113,"char_repetition_ratio":0.124096684,"word_repetition_ratio":0.054628223,"special_character_ratio":0.27707243,"punctuation_ratio":0.10108303,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.99999344,"pos_list":[0],"im_url_duplicate_count":[null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2020-12-01T13:59:22Z\",\"WARC-Record-ID\":\"<urn:uuid:d638a3cf-664b-4c17-9e45-8286151fb72d>\",\"Content-Length\":\"6854\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:5187115f-8212-4b39-be8e-86eb3ff69b08>\",\"WARC-Concurrent-To\":\"<urn:uuid:e98db242-d185-490f-b4e7-4fd59b725174>\",\"WARC-IP-Address\":\"141.2.6.106\",\"WARC-Target-URI\":\"http://www.thi.informatik.uni-frankfurt.de/~jukna/greedy1.html\",\"WARC-Payload-Digest\":\"sha1:JPTG53TRLEPMTSQMROP24AAWEXT65GS6\",\"WARC-Block-Digest\":\"sha1:QBJ2V4MSQJBG572VH7JCEC3HBTJ4P6EA\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2020/CC-MAIN-2020-50/CC-MAIN-2020-50_segments_1606141674594.59_warc_CC-MAIN-20201201135627-20201201165627-00219.warc.gz\"}"}