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

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

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

Exercise 10.13 in the book asks to prove the following

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.Theorem 4[Korte-Hausman 1978]: The intersection of $k$ matroids is a $k$-matroid.

**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:

- T.A. Jenkyns. The efficacy of the ``greedy'' algorithm. In {\em Proc. of the 7th Southeastern Conf. on Combinatorics, Graph Theory, and Computing, Utilitas Mathematica, Winnipeg}, pages 341-350, 1976.
- B. Korte and D. Hausmann, An analysis of the greedy heuristic for independence systems,
*Annals of Discrete Mathematics*, 2 (1978), 65-74. Local copy. - D. Hausmann and B. Korte,
Lower bounds on the worst-case complexity of some oracle algorithms,
*Discrete Math.*, 24(3) (1978), 261-276.

Return to the home page of the 2nd edition