Given a weight function $w:X\to{\Bbb R}_+$, the goal is to maximize $w(A)=\sum_{x\in A}w(x)$ over all $A\in{\cal F}$. Let $A_o$ denote an optimal solution, and $A_g$ the solution given by the greedy algorithm. We have shown in the book (Theorem 10.8) that the performance ratio $w(A_g)/w(A_o)$ is at least $1/k$ if and only if ${\cal F}$ is a $k$-matroid. We now give an alternate and simpler proof of Theorem 10.8. For a subset $S\subseteq X$, define its lower rank $lr(S)$ and upper rank $ur(S)$ by:
$lr(S)$ :=min{$|F|$: $F$ is a maximal independent subset of $S$}
$ur(S)$ :=max{$|F|$: $F$ is a maximal independent subset of $S$}
Obviously, if ${\cal F}$ is a matroid then $lr(S)=ur(S)$ for any $S\subseteq X$. Hence, the rank quotient $$ p({\cal F}):=\min_{S\subseteq X}\frac{lr(S)}{ur(S)} $$ can be interpreted as a measure of how much ${\cal F}$ differs from being a matroid. In terms of Sect. 10.3, we have that \[ \mbox{$p({\cal F})\geq 1/k$ iff ${\cal F}$ is $k$-balanced iff ${\cal F}$ is a $k$-matroid.} \]
Theorem 1 [Jenkyns 1976]: For every system ${\cal F}$ and every weighting $w$, the performance ratio of the greedy algorithm satisfies $$ \frac{w(A_g)}{w(A_o)}\geq p({\cal F}). $$Proof: (Due to Korte and Hausman 1978) Recall that the greedy algorithm first sorts the elements $x_1,x_2,\ldots,x_n$ of $X$ by weight, heaviest first. Then it starts with $A=\emptyset$ and in the $i$-th step adds the element $x_i$ to the current set $A$ if and only if the result still belongs to ${\cal F}$ (is an independent set). Setting $X_i:=\{x_1,\ldots,x_i\}$, this implies that the solution $A_g\subseteq X$ given by the greedy algorithm must be such that $A_g\cap X_i$ is a maximal independent subset of $X_i$ for all $i=1,\ldots,n$.
Setting $w(x_{n+1}):=0$ we obtain through a suitable summation that $$ w(A_g)=\sum_{i=1}^n|A_g\cap X_i|(w(x_i)-w(x_{i+1})) \ \ \ \mbox{ and }\ \ \ w(A_o)=\sum_{i=1}^n|A_o\cap X_i|(w(x_i)-w(x_{i+1})). $$ As $A_o\cap X_i\subseteq A_o\in{\cal F}$ we have $|A_o\cap X_i|\leq ur(X_i)$. By the definition of $A_g$, $A_g\cap X_i$ is a maximal independent subset of $X_i$. Hence, $A_g\cap X_i|\geq lr(X_i)$ and thus $$ |A_g\cap X_i|\geq |A_o\cap X_i|\cdot\frac{lr(X_i)}{ur(X_i)} \geq |A_o\cap X_i|\cdot \min_{S\subseteq X}\frac{lr(S)}{ur(S)}=p({\cal F}). $$ Form the previous expressions for $w(A_g)$ and $w(A_o)$ we obtain that $w(A_g)\geq p({\cal F})\cdot w(A_o)$, and desired. $\Box$
The lower bound on the performance ration given in Theorem 1 cannot be improved.
Theorem 2: For every system ${\cal F}$ there exists a weighting $w:X\to\{0,1\}$ such that $w(A_g)/w(A_o)=p({\cal F})$.Proof: Take a subset $S_0\subseteq X$ for which $p({\cal F})=lr(S_0)/ur(S_0)$, and let $F_l$ and $F_u$ be the corresponding subsets of $S_0$ with $|F_l|=lr(S_0)$ and $|F_u|=ur(S_0)$. Define the weighting $w:X\to\{0,1\}$ by $w(x)=1$ iff $x\in S_0$. Now order the elements $x_1,\ldots,x_n$ of $X$ is such a way that first come the elements of $F_l$, then the remaining elements of $S_0$, and finally the remining elements of $X$. It is clear that $w(x_1)\geq w(x_2)\geq \ldots\geq w(x_n)$. The greedy algorithm outputs the set $A_g=F_l$, whereas the optimum value is $w(A_o)\geq w(F_u)$. Hence $$ \frac{w(A_g)}{w(A_o)}\leq \frac{w(F_l)}{w(F_u)}=\frac{|F_l|}{|F_u|}=p({\cal F}). $$ $\Box$
Thus, greedy algorithms cannot achieve better approximation factor that $p({\cal F})$. In fact, the same holds for any(!) polynomial time algorithm based on "oracle queries". An oracle algorithm takes an input $(w,{\cal F})$, and outputs some set $A\in{\cal F}$ as a solution. The restriction is that the algorithm can only ask questions of the form "is a set $S$ in ${\cal F}$?". As an answer $A$ the algorithm can then output any of the sets $S$ for which the answer was "yes". The decision of which of these "yes" sets to output is up to the algorithm. Moreover, the algorithm can be "adaptive": what set $S$ to ask may depend on the sets asked so far, as well on the answers for these sets. The time spent by the algorithm is the maximum, over all inputs $(w,{\cal F})$, of the number of queries made on this input.
Note that the greedy algorithm is an oracle algorithm with $n$ queries of the form "is the set $S\cup\{x_i\}$ in ${\cal F}$?", where $S$ is the set on which the algorithm answered YES for the last time, and $x_i$ is the next treated element.
In the next theorem we consider special inputs $(w,{\cal F})$ where the weight function $w$ is trivial ($w(x)=1$ for all $x\in X$), and ${\cal F}$ consists of all subsets $F\subset X$ of size $|F| \leq m-1$ plus some single set $F_0$ of size exactly $m$; here $m\leq n/2$. Note that the rank quotient for every such system ${\cal F}$ is $p({\cal F})= (m-1)/m$.
Theorem 3 [Hausman-Korte 1978]: No oracle algorithm working on special inputs $(w,{\cal F})$ in time shorter than ${n}\choose{m}$ can achieve an approximation ratio better than $p({\cal F})$.Proof: Suppose we have an oracle algorithm that works in time $r < {{n}\choose{m}}$. We can view the algorithm as a "decision tree", at each node of which some query of the form "is a set $S$ in ${\cal F}$?" is made. We construct a path $P$ in this tree as follows: at least node making a test on a set $S$, choose the YES-edge if and only if $|S| < m$. Since every path (including the constructed one) has length $r < {{n}\choose{m}}$, there is a set $S_0$ of size $|S_0|=m$ which was not queried along the constructed path. Now let ${\cal F}$ be a system consisting of $S_0$ and all sets of size $< m$. Then, on input ${\cal F}$, the algorithm follows the constructed path and outputs some set $A\in {\cal F}$ of size $|A| < m$. Since the optimal solution is $S_0$, the achieved approximation factor is $\leq |A|/|S_0|\leq (m-1)/m=p({\cal F})$, as claimed. $\Box$
Exercise 10.13 in the book asks to prove the following
Theorem 4 [Korte-Hausman 1978]: The intersection of $k$ matroids is a $k$-matroid.The hint invites to show that the intersection of $k$ $1$-extendible system is $k$-extendible, and to use Lemma 10.10. Here we give a more direct proof. Namely, we show that the interseciton of $k$ matroids is $k$-balanced.
Proof: Let ${\cal F}^1,\ldots,{\cal F}^k$ be $k$ matroids over the same ground-set $X$, and ${\cal F}=\bigcap_{i=1}^k{\cal F}^i$.
For $i=1,\ldots,k$, let $A_i$ be a maximal ${\cal F}^i$-independent subset of $A\cup B$ containing $A$, and let let $B_i$ be a maximal ${\cal F}^i$-independent subset of $A\cup B$ containing $B$. If there were an element $x\in B\setminus A$ with $x\in \bigcap_{i=1}^k A_i\setminus A$, then the extended set $A\cup\{x\}$ would lie in the intersection $\bigcap_{i=1}^k A^i$, and hence, would be an ${\cal F}$-independent set, a contradiction to the maximality of $A$. Thus, each element $x\in B\setminus A$ can belong to at most $k-1$ of the sets $A_1\setminus A,\ldots,A_k\setminus A$. Since $A\subseteq A_i\subseteq A\cup B$, we have that $A_i\setminus A\subseteq B\setminus A$ holds for all $i=1,\ldots,k$. So, if $d(x)$ denotes the number of sets $A_i\setminus A$ containing an element $x$, then $d(x)\leq k-1$ for all $x\in B\setminus A$. This yields \[ \sum_{i=1}^k|A_i|-k|A|=\sum_{i=1}^k|A_i\setminus A| =\sum_{x\in B\setminus A}d(x)\leq (k-1)|B\setminus A| \leq (k-1)|B|. \] By the definition of a matroid, we have that \[ \mbox{$|A_i|=|B_i|$ holds for all $i=1,\ldots,k$.} \] Moreover, $B\subseteq B_i$ for all $i$ implies that $\sum_{i=1}^k-k|B|\geq 0$. Hence, the above inequality $(k-1)|B|\geq \sum_{i=1}^k|A_i|-k|A|$ implies \[ |B|\leq \left(\sum_{i=1}^k|B_i|-k|B|\right)+|B| =\sum_{i=1}^k|A_i|-(k-1)|B| \leq \sum_{i=1}^k|A_i|-\left( \sum_{i=1}^k|A_i|-k|A|\right) =k|A|, \] as desired. $\Box$
Related literature: