\input amstex
\input amsppt.sty

\nologo

\magnification1200
\hsize13cm
\vsize19cm

\def\al{\alpha}
\def\be{\beta}
\def\F{\Cal F}

\topmatter 
\title The Greedy Algorithm as a Combinatorial Principle
\endtitle 
\author U. Faigle
\endauthor 
\address 
Fachbereich Mathematik, Technische Hochschule Darmstadt, D-6100
Darmstadt, Germany
\endaddress

\endtopmatter
\document

One of the best known results of combinatorial matching theory is
Hall's ``marriage theorem". In fact, matching theory may be based on
this theorem (cf\. \cite{5}). It can either be proved directly or
derived from stronger theories, e.g., the theory of flows in networks
\cite{4} or the theory of polyhedral matroids \cite{2}. The latter
theories are both usually seen as manifestations of the duality
principle in linear programming --- an ``explanation" which is not
very satisfactory from a purely combinatorial point of view.

In this note, we want to give an outline how a combinatorial theory
including, in particular, matching theory may be based on a very
simple combinatorial principle. This principle states that, under
certain restrictions, an optimal combinatorial object can be
constructed in a straight-forward manner, namely by the ``greedy
algorithm". 

It seems to be an open problem to give a definition of
``combinatorics" which everyone agrees upon. For our purposes, the
following standpoint is appropriate: combinatorics is the study of the
processes involved in building up a combinatorial object step by step
so that certain requirements are met (cf\. \cite{8}). What we study
here are the implications if we know that an optimal combinatorial
object can be obtained by taking the greedy algorithm as our rule of
construction.

\vskip10pt
\subhead The Greedy Algorithm\endsubhead
\vskip10pt

Let $P$ be a (finite) partially ordered set. A {\it sequential family}
(over $P$) is a non-empty collection $S$ of sequences $\al=(x_1,x_2,
\dots)$, $x_i\in P$, such that 

\roster 
\item "(S$_1$)" for every $\al=(x_1,x_2,\dots)\in S$, $x_i\le x_j$
implies $i\le j$,\newline 
(in particular: $\vert\al\vert\le \vert P\vert$).
\item "(S$_2$)" for every $\al=(x_1,\dots,x_k)\in S$, $0\le m\le k$,
$\al_m=(x_1,\dots,x_m )\in S$.\newline
 We define $\al_0=\emptyset$ and $\vert
\al_0\vert=0$. 
\endroster

A ({\it compatible}) {\it weighting} of $P$ is a function $w:P\to \Bbb
R$ such that $x\le y$ implies $w(x)\ge w(y)$. (Note that $w$ reverses
the order.)

$w$ extends to a weighting of $S$ via
$$w(\al)=\cases \sum _{x\in \al} ^{}w(\al)&\text{if
}\emptyset\ne\al\in S,\\
0&\text{if }\al=\emptyset.\endcases$$

The combinatorial object we seek to construct is an element $\al\in S$
such that $w(\al)$ is maximal.

The {\it greedy algorithm} now is the following procedure:

\smallskip
{\it Step 1}: Choose $x_1\in P$ such that $w(x_1)$ is maximal under
the conditions: $w(x_1)>0$ and $(x_1)\in S$. If no such choice is
possible, stop. Otherwise continue.

\hbox to13cm{\leaders \hbox to1em{\hss.\hss}\hfill}

{\it Step $k$}: Choose $x_k\in P\backslash \{x_1,\dots,x_{k-1}\}$ 
such that $w(x_k)$ is maximal under
the conditions: $0<w(x_k)\le w(x_{k-1})$ and $(x_1,\dots,x_{k-1},x_k)
\in S$. If no such choice is
possible, stop. Otherwise continue.

\smallskip

In other words, if we list the positive elements of $P$ in some linear
order $x,y,z,\dots$ so that $w(x)\ge w(y)\ge w(z)\ge\cdots>0$, the
greedy algorithm proceeds from one element to the next and adjoins the
element to the sequence already constructed if the resulting sequence
is a member of $S$.

As the greedy algorithm will not necessarily produce an optimal
sequence for an arbitrary sequential family $S$, we have to
characterize those families for which it does.

\proclaim{Theorem \rm\cite{3}} The greedy algorithm produces, for
every weighting of $P$, an optmimal sequence of $S$ if and only if $S$
satisfies the two conditions:

\roster 
\item "(GS$_1$)" for every $\al,\be\in S$ with
$\vert\al\vert<\vert\be\vert$, there is an $x\in\be$ and $y\le x$ such
that $(\al,y)\in S$.
\item "(GS$_2$)" if $A\subseteq B$ are ideals of $P$, $p\in A$ an
isthmus of $S(B)$, then $p$ is an isthmus of $S(A)$.\quad \quad \qed
\endroster
\endproclaim

Thereby we call $p\in P$ an {\it isthmus} of $S$ is $p$ occurs in
every {\it basis} of $S$, i.e., in every $\be\in S$ such that
$\vert\be\vert=\max\{\vert\al\vert:\al\in S\}$.

Furthermore, we define for an ideal $A\subseteq P$,
$$S(A)=\{\al\in S:\al\subseteq A\}.$$
Finally, an ({\it order}) {\it ideal} of $P$ is a subset $A\subseteq
P$ such that $x\in A$ and $y\le x$ imply $y\in A$.

\vskip10pt
\subhead Rank Functions\endsubhead
\vskip10pt

Assume from now on that the sequential family $S$ satisfies properties
(GS$_1$) and (GS$_2$), and consider the collection $\F=\F(P)$ of all
ideals of $P$.

$\F$ is a distributive lattice with respect to union and
intersection. Moreover, via
$$\text{for }A\in \F, \ r(A)=\max\{\vert\al\vert:\al\in S(A)\},\tag1$$
$S$ induces a {\it rank function} $r$ on $\F$, i.e.,

\roster 
\item "(R$_0$)" $r(\emptyset)=0$,
\item "(R$_1$)" for $A\subseteq B\in\F$, $0\le r(B)-r(A)\le \vert
B-A\vert$,
\item "(R$_2$)" for $A,B\in\F$, $r(A\cup B)+r(A\cap B)\le r(A)+r(B)$.
\endroster

One can show that every rank function on $\F$ arises this way.

Another construction to obtain rank functions is essentially due to
Dilworth (see \cite{1}):

Say that the function $f:\F\to\Bbb N$ is a {\it pre-rank function} if
$f$ satisfies (R$_0$) and (R$_2$) and the weaker property

\roster 
\item "(R$_1'$)" for $A\subseteq B\in \F$, $r(A)\le r(B)$.
\endroster
\noindent
$f$ induces a rank function $r$ on $\F$ via
$$\text{for }a\in\F,\ r(A)=\min\{\vert A-B\vert+f(B):B\in\F\}.\tag2$$

Note that formulas (1) and (2) capture a mini-max principle for a rank
function $r$ on $\F$ which lies at the heart of matching theory.

We could now develop the theory of (integral) polyhedral matroids (see
\cite{2}, \cite{6}) by specializing to the case where $\F$ is the set
of all vectors with integer coefficients in $\Bbb R^n$ that are less
than or equal to some non-negative vector $c\in \Bbb R^n$ ($c$ would
then play the role of a ``capacity restriction").

But let us instead turn to an even more special and much-studied case:
the case where $P$ is trivially ordered.

\vskip10pt
\subhead Matroids\endsubhead
\vskip10pt

If $P$ is trivially ordered, $\F(P)$ is just the collection of all
subsets of $P$. The properties (R$_0$), (R$_1$), and (R$_2$) then are
the defining properties of a {\it matroid\/} in terms of its rank
function (see, e.g., \cite{7}). 

A subset $X\subseteq P$ is {\it
independent\/} if
$$r(X)=\vert X\vert.\tag $1'$ $$
Thus the independent sets are exactly the subsets of $P$ whose
arrangements make up the sequences of the corresponding sequential
family $S$. 

On the other hand, if the matroid is derived from the pre-rank
function $f$, an independent set $X\subseteq P$ is characterized by
$$\text{for }A\in\F,\ f(A)\ge \vert X\cap A\vert.\tag $2'$ $$

We may illustrate the formulas ($1'$) and ($2'$) as follows:

If $G=(U\cup V,E)$ is a bipartite graph, define for every $A\subseteq
V$,
$$f(A)={}\text{number of vertices of $U$ related to vertices of $A$.}$$
$f$ clearly is a pre-rank function on $\F(V)$. To say that $V$ is
independent in the associated matroid, means according to ($2'$):
$$f(A)\ge\vert A\vert \quad \text{for all }A\subseteq V.$$
This is Hall's condition for the existence of a matching from $U$ onto
$V$.

Let us remark that, within the context of polyhedral matroids, one can
{\it prove} Hall's marriage theorem just by suitably interpreting the
formulas analogous to ($1'$) and ($2'$).

If we accept Hall's theorem, property (GS$_1$) of the underlying
sequential family immediately implies that every (partial)
matching can be augmented to a maximal matching. This, of course, also
follows from the augmentation path theorem. But we do not need it to
derive this information.

\Refs
\ref\no 1\by P. Crawley and R. P. Dilworth\book Algebraic Theory of
Lattices \publ Prentice--Hall\publaddr Englewood Cliffs, N.J.\yr 1973\endref

\ref\no 2\by J. Edmonds\paper Submodular functions, matroids and
certain polyhedra\inbook Proc\. Int\. Conf\. on Combinatorics
(Calgary)\publ Gordon and Breach\publaddr New York\yr 1970\pages
69--87\endref 

\ref\no 3\by U. Faigle\paper The greedy algorithm for partially
ordered sets\jour Discrete Math\.\vol 28\yr 1979\pages 153--159\endref

\ref\no 4\by L. R. Ford and D. R. Fulkerson\book Flows in
Networks\publ Princeton University Press\publaddr Princeton\yr 1962\endref

\ref\no 5\by L. H. Harper and G.-C. Rota\paper Matching theory: an
introduction\jour Adv\. Probab\.\vol 1\yr 1971\pages 169--213\endref

\ref\no 6\by C. J. H. McDiarmid\paper Rado's theorem for
polymatroids\jour Math\. Proc\. Cambridge Philos\. Soc\.\vol 78\yr
1975\pages 263--281 \endref

\ref\no 7\by D. J. A. Welsh\book Matroid Theory\publ Academic
Press\publaddr London\yr 1976\endref

\ref\no 8\by H. S. Wilf\paper A unified setting for sequencing,
ranking, and selection algorithms for combinatorial objects\jour
Adv\. Math\.\vol 24\yr 1977\pages 281--291\endref

\endRefs






\enddocument
