\input amstex
%\input amsppt.sty

\magnification1200

\UseAMSsymbols

\NoBlackBoxes

\parindent=0pt

\centerline{Valuated Matroids}
\centerline{-- A new Look at the Greedy Algorithm}
\bigskip
\centerline{by}
\bigskip
\centerline{Andreas W.M. Dress and Walter Wenzel}
\bigskip
{\bf Abstract:} {\it In this note we study a variant of the greedy algorithm
for} {\bf weight
functions} {\it defined on the system of m-subsets of a given set $E$ and
characterize completely those classes of weight functions for which this
algorithm works. Well known examples come from matroid theory, new ones
come from valuation theory.}\newline
{\bf Key words and phrases:} {\it Combinatorial optimization, greedy algorithm,
combinatorial geometries,
matroids, representation theory of matroids, valuations of fields,
Grassmann-Pl\"ucker identities, greedoids.}
\medskip
{\bf Introduction} When matroids were defined in 1935 by H. Whitney, they served the
purpose of clarifying on an abstract level the concept of linear (in)dependence.
It took more than thirty years before D. Gale observed 1968 in [G], based
on earlier work of J.B. Kruskal [K] and R. Rado [R], that they can also
be defined by means of their close relationship with {\it greedy algorithms}.
More precisely, he showed that given a finite set $E$ and a family $\Cal
J$ of subsets of $E$ with ``$J\subseteq I\in \Cal J\Rightarrow J\in \Cal
J$'' we can find for any map $w$ from $E$ into the set $\Bbb R_+$ of
nonnegative real numbers a set $I=I_{max}\in \Cal J$ with $f(I):=\sum \limits
_{x\in I}f(x)\ge f(J)$ for all $j\in \Cal J$ by using the greedy algorithm
(that is by first choosing an element $x_1\in E$ with $\{ x_1\} \in \Cal
J$ and $f(x_1)=max(f(y)\ |\ \{ y\} \in \Cal J)$, then an element $x_2\in
E\setminus \{ x_1\} $ with $\{ x_1,x_2\} \in \Cal J$ and $f(x_2)=max(f(y)\
|\ \{ x_1,y\} \in \Cal J,y\ne x_1)$ and so on) if and only if $\Cal J$ is
the set of independent subsets of $E$ with respect to some matroid $M$,
defined on $E$.
\smallskip
Since then, many further interesting relations between the feasibility of
greedy algorithms and various combinatorial structures have been discovered
(cf. ...)
and proved to be rather useful in combinatorial optimization.
In this note we want to discuss an apparently new perspective in this context.
We start with the observation that in the situation studied by Gale one
knows in advance that the resulting set $I_{max}$ is necessarily a basis
of the matroid $M$, that is, it is a maximal subset of $\Cal J$. According
to ..., this can be used to speed up the optimization process a little bit
as follows: start with an arbitrary basis $B=\{ e_1,\hdots,e_m\} $ of $M$,
then choose $x_1\in E$ such that $B_1:=\{ x_1,e_2,\hdots,e_m\} $ is a basis,
too, and $f(B_1)\ge f(\{ x,e_2,\hdots,e_m\} )$ for all bases $\{
x,e_2,\hdots,e_m\} $. Then replace $e_2$ by some $x_2\in E$ for which $B_2;=\{
x_1,x_2,e_3,\hdots,e_m\} $ is a basis and $f(B_2)\ge (\{ x_1,xe_3,\hdots,e_m\}
)$ for all bases $\{ x_1,x,e_3,\hdots,e_m\} $ and so on. Then we have $f(\{
x_1,\hdots,x_m\} )\ge f(J)$ for all $J\in \Cal J$. One therefore may ask
for an arbitrary map $v$ from the set $\tbinom {E} {m}$ of all 
$m$-subsets of $E$ into $\Bbb R\cup \{ -\infty\} $ 
for conditions
under which the corresponding algorithm of replacing the elements
$e_1,\hdots,e_m$ of some $m$-subset $\{ e_1,\hdots,e_m\} $ of $E$ with $v(\{
e_1,\hdots,e_m\} )\ne -\infty $ consecutively by some $x_1,\hdots,x_m$ in
a locally optimal or {\it greedy} fashion, the resulting set $\{ x_1,\hdots,x_m\}
$ satisfies $v(\{ x_1,\hdots,x_m\} )\ge v(\{ y_1,\hdots,y_m\} )$ for all
$m$-subsets $\{ y_1,\hdots,y_m\} $ of $E$.
\medskip
This question has a surprisingly simple answer if, as suggested by D. Gale's
result,
one modifies it as follows: Given some $v:\tbinom {E} {m} \rightarrow
\Bbb R\cup \{ -\infty \} $ with $v(\tbinom {E} {m} )\ne \{ -\infty \} $,
find necessary and sufficient conditions for $v$ such that for all maps
$\varphi :E\rightarrow \Bbb R$ the maximal value of $v_{\varphi}:\tbinom
{E} {m}\rightarrow \Bbb R\cup \{ -\infty \} $ given by
$$
v_{\varphi}(\{ e_1,\hdots,e_m\} ):=v(\{ e_1,\hdots,e_m\} )+\varphi (e_1)+\hdots
+\varphi (e_m)
$$
can be found by the greedy algorithm, explained above. As we will show,
this is possible for all $\varphi :E\rightarrow \Bbb R$ if and only if the
following variant of the matroid exchange property holds:
\smallskip

\parindent=1truecm
\item{(V1)} {\it For all $B_1,B_2\in \tbinom {E} {m}$ and $e\in B_1\setminus
B_2$ there exists
some $f\in B_2\setminus B_1$ with \linebreak
$$v(B_1)+v(B_2)\le v((B_1\setminus \{ e\}
)\cup \{ f\} )+v((B_2\setminus \{ f\} )\cup \{ e\} ).$$}

\parindent=0pt
Interesting examples of maps $v: \tbinom {E} {m}\rightarrow \Bbb R\cup \{
-\infty \} $, satisfying this condition, come -- surprisingly enough --
from $p$-adic analysis (or, more generally, from valuation theory -- actually,
it was in this context, where the above condition occured first, (see [DW1]):
\smallskip
If $E$ is a finite subset of $\Bbb Q^m$ which spans $\Bbb Q^m$, then the
Grassmann-Pl\"ucker relations imply that for a given prime number $p$ the
map $v_p:\tbinom {E} {m}\rightarrow \Bbb R\cup \{ -\infty \} $ defined by
$$
v_p(\{ e_1,\hdots,e_m\} ):=\cases -\infty & \text { if } det (e_1,\hdots,e_m)=0\\
n & \text { if } det (e_1,\hdots,e_m)=p^{-n}\cdot \tfrac {a} {b}\\ {} &
\text { with } n\in \Bbb Z,a,b\in \Bbb Z\setminus p\cdot \Bbb Z\endcases
$$
satisfies our condition. Hence, as an application of our result, one could
compute a basis $e_1,\hdots,e_m$ of $\Bbb Q^m$, contained in $E$, for which
the p-part of $det (e_1,\hdots,e_m)$ is as small as possible, by the above
greedy algorithm. 
\medskip
It may also be interesting to review later work on the greedy algorithm
from this perspective, in particular the work of $B$. Korte and L. Lovasz
on greedoids (cf. [...]).
\medskip
In the sequel we assume that $E$ is some finite set and $m\in \Bbb N$ satisfies
$m\le \# E$.
\medskip
For a map $v:\tbinom {E} {m}\rightarrow \Bbb R\cup \{ -\infty \} $ we put
$$
v(e_1,\hdots,e_m):=\cases v(\{ e_1,\hdots,e_m\} ) & \text { if } \{
e_1,\hdots,e_m\} \in \tbinom {E} {m}\\
-\infty & \text { otherwise } . \endcases
$$
{\bf Definition 1: A valuated matroid of rank $m$ with values in $\Bbb R$},
is a pair $(E,v)$, consisting of a finite set $E$ with $\# E\ge m$ together
with a map $v:\tbinom {E} {m}\rightarrow \Bbb R\cup \{ -\infty \} $ satisfying
(V1) and
$$
\text { there exists some } B\in \tbinom {E} {m} \text { with } v(B)\ne
-\infty . \tag V0
$$
An $m$-set $B\in \tbinom {E} {m}$ is called a {\bf basis} of the valuated
matroid $(E,v)$, if $v(B)\ne -\infty$.

\parindent=4truecm
\item{{\bf Remarks:}i)} By (V1) it is clear that the bases of a valuated
matroid are also the bases of a combinatorial geometry (or matroid in the
classical sense). Vice versa, if $M$ is a combinatorial geometry of rank
$m$, defined on $E$, then any map $v$ from $\tbinom {E} {m}$ into $\Bbb
R\cup \{ -\infty \} $ which satisfies (V0) and (V1) is called a valuation
of $M$, if for all $B\in \tbinom {E} {m}$ one has $v(B)\ne -\infty $ if
and only if $B$ is a basis of $M$.
\item{ii)} A valuation $v:\tbinom {E} {m}\rightarrow \Bbb R\cup \{ -\infty
\} $ is called {\bf trivial}, if there exists some $\alpha \in \Bbb R$ with
$v(B)\in \{ \alpha ,-\infty \} $ for all $B\in \tbinom {E} {m}$.

\parindent=0pt
\medskip
Every combinatorial geometry $M$ of rank $m$, defined on $E$, has a trivial
valuation $v:\tbinom {E} {m}\rightarrow \Bbb R\cup \{ -\infty \} $, namely
$$
v(B):=\cases 0 & \text { if } B \text { is a base of } M\\
-\infty & \text { otherwise } . \endcases
$$
This is nothing but a reformulation of the strong exchange property for
bases of $M$.
\medskip
{\bf Definition 2:} Assume $v:\tbinom {E} {m}\rightarrow \Bbb R\cup \{ -\infty
\} $ is some map with $v(B)\ne -\infty $ for at least one $B\in \tbinom
{E} {m}$. The {\bf greedy algorithm} 
runs as follows:

\parindent=5truecm
\item{Step $0:$} Choose some $e_1,\hdots,e_m\in E$ with $v(\{ e_1,\hdots,e_m\}
)\ne
-\infty$.
\item{Step $k (1\le k\le m):$} Assume that $x_1,\hdots,x_{k-1}\in E$ are already determined
and choose some 
$x_k\in E$ such that
$$
v(\{ x_1,\hdots,x_k,e_{k+1},\hdots,e_m\} )\ge
v(\{ x_1,\hdots,x_{k-1},x,e_{k+1},\hdots,e_m\} ) 
$$
for all $x\in E$.
\medskip

\parindent=0pt
We say that the greedy algorithm {\bf works} for $v$ if for all starting
sequences 
$e_1,\hdots,e_m\in E$ with $v(\{ e_1,\hdots,e_m\} )\ne -\infty$
and all permitted choices of the $x_1,\hdots,x_m$ one has\linebreak $v(\{
x_1,\hdots,x_m\} )\ge
v(B)$ for all $B\in \tbinom {E} {m}$ in which case $v$ is called
{\bf admissible}.
\medskip
For $e_1,\hdots,e_{m-1}\in E$ put
$$
\align & M_v(e_1,\hdots,e_{m-1})\\
& :=\{ x\in E\ |\ v(e_1,\hdots,e_{m-1},x)\ge v(e_1,\hdots,e_{m-1},y) \text
{ for all } y\in E\} . \endalign
$$
Obviously, $v$ is admissible if and only if for all $e_1,\hdots,e_m\in E$
with $v(e_1,\hdots,e_m)\ne -\infty $ and all $x_1,\hdots,x_m\in E$ with
$$
x_i\in M_v(x_1,\hdots,x_{i-1},e_{i+1},\hdots,e_m) \text { for } 1\le i\le
m
$$
we have $v(x_1,\hdots,x_m)\ge v(y_1,\hdots,y_m)$ for all $y_1,\hdots,y_m\in
E$.
\medskip
{\bf Definition 3:} Two maps $v,w:\tbinom {E} {m}\rightarrow \Bbb R\cup
\{ -\infty \} $ are called {\bf projectively equivalent}, if there exists
some $\alpha \in \Bbb R$ and some map $\varphi :E\rightarrow \Bbb R$ such
that
$$
w(e-1,\hdots,e_m)=\alpha +\sum \limits _{i=1}^m\varphi (e_i)+v(e_1,\hdots,e_m)
\text { for all } e_1,\hdots,e_m\in E.
$$
If this is the case, we write $w:=v(\alpha ,\varphi)$.
\medskip
{\bf Remark:} If $v:\tbinom {E} {m}\rightarrow \Bbb R\cup \{ -\infty \}
$ is a valuation of some combinatorial geometry $M$, then it is clear that
$v(\alpha ,\varphi)$ is also a valuation of $M$ for all $\alpha \in \Bbb
R$ and all maps $\varphi :E\rightarrow \Bbb R$.
\medskip
Now we can show
\medskip
{\bf Theorem:} 
Assume $E$ is a finite set with $\# E\ge m$ and $v:\tbinom {E} {m}\rightarrow
\Bbb R\cup \{ -\infty \} $ is some
map satisfying (V0). Then
$(E,v)$ is a valuated matroid, if and only if
the greedy algorithm works for $v_{\varphi}$ for all $\alpha \in \Bbb R$
and all
maps $\varphi :E\rightarrow \Bbb R$.
\medskip
{\bf Proof:}
At first we assume that $v$ is a valuation of some combinatorial geometry
$M$, defined of $E$. By the last remark it is enough to show that $v$ is admissible.
\medskip
Assume $e_1,\hdots,e_m\in E$ with $v(\{ e_1,\hdots,e_m\} )\ne 0$ and 
$x_1,\hdots,x_m\in E$ such that $x_i\in M_v(x_1,\hdots,x_{i-1},e_{i+1},\hdots,
e_m)$ for $1\le i\le m$. 
Put $B_0:=\{
x_1,\hdots,x_m\} $. We must prove
$$
v(B)\le v(B_0) \text { for all } B\in \tbinom {E} {m}. \tag 1
$$
At first we show
$$
v((B_0\setminus x_j)\cup x)\le v(B_0) \text { for } 1\le j\le m \text { and
all } x\in E. \tag 2
$$
By our assumption (2) is clear for $j=m$.
\medskip
To prove (2) for $1\le j\le m-1$ we may assume by induction that
$$
v((B_0\setminus \{ x_j,x_m\} )\cup \{ x,e_m\} )\le v((B_0\setminus x_m)\cup
e_m) \text { for all } x\in E, \tag 2a
$$
because $v':\tbinom {E\setminus e_m} {m-1}\rightarrow \Bbb R\cup \{ -\infty
\} $ defined by
$$
v'(A):=v(A\cup e_m)\ (A\in \tbinom {E\setminus e_m} {m})
$$
is obviously a valuation of the contraction $M':=M/\{ e_m\} $ of rank $m-1$. 
\medskip
Now assume $v((B_0\setminus x_j)\cup x)\ne -\infty$ for some fixed $j$ with
$1\le j\le m-1$ and some fixed $x\in E$. Consider the bases $B_1:=(B_0\setminus
x_m)\cup e_m$ and $B_2:=(B_0\setminus x_j)\cup x$ of $M$.
(2) clearly holds in case $x_j=x$. Otherwise we have $x_j\in B_1\setminus
B_2$. Thus there exists $e\in B_2\setminus B_1\subseteq \{ x_m,x\} $ with
$$
v(B_1)+v(B_2)\le v((B_1\setminus x_j)\cup e)+v((B_2\setminus e)\cup x_j).
$$
But (2a) yields $v((B_1\setminus x_j)\cup e)\le v(B_1)$ and thus
$$
v(B_2)\le ((b_2\setminus e)\cup x_j). \tag 2b
$$
Furthermore, we have $\{ x_1,\hdots,x_{m-1}\} \subseteq (B_2\setminus e)\cup
x_j$, and thus our choice of $x_m$ implies
$$
v((B_2\setminus e)\cup x_j)\le v(B). \tag 2c
$$
(2) follows now from (2b) and (2c).
\medskip
Now we derive (1) from (2) by induction on $n:=\# (\{ y_1,\hdots,y_m\}
\setminus \{ x_1,\hdots,x_m\} )$. The cases $n=0$ and $v(y_1,\hdots,y_m)=0$
are trivial, while for $n=1$ we are done by (2).
\medskip
Now assume $2\le n\le m$, say, $\# \{ y_1,\hdots,y_n,x_1,\hdots,x_m\} =n+m$
and $y_k=x_k$ for $n+1\le k\le m$. Then by (V1), (2) and our induction
hypothesis there exists $i$ with $1\le i\le n$ and 
$$
\align & v(\{ y_1,\hdots,y_n,x_{n+1},\hdots,x_m\} )+v(B_0)\\
\le & v(\{ x_i,y_2,\hdots,y_n,x_{n+1},\hdots,x_m\} )+v((B_0\setminus x_i)\cup y_1)\\
\le & 2\cdot v(B_0).\endalign
$$
Since $v(B_0)\ge v(\{ e_1,\hdots,e_m\} )>-\infty$, this means
$$
v(y_1,\hdots,y_n,x_{n+1},\hdots,x_m)\le v(B_0).
$$
Now assume that, vice versa, $v_{\varphi}$ is admissible for all
$\alpha \in \Bbb R$ and all maps $\varphi :E\rightarrow \Bbb R$. We have
to show that $v$ satisfies (V1). Otherwise assume
$e_1,\hdots,e_m,f_1,\hdots,f_m\in E$ are such that for $B_1:=\{
e_1,\hdots,e_m\} $ and $B_2:=\{ f_1,\hdots,f_m\} $ we have
$$
v(B_1)+v(B_2)>v((B_2\setminus f_i)\cup e_1)+v((B_1\setminus e_1)\cup f_i)
\tag 3
$$
for all $i$ with $1\le i\le m$.
Then we must have $e_1\notin B_2$ and $v(B_2)\ne -\infty$.
\medskip
Since $E$ is finite, we can choose some $\gamma \in \Bbb R$ such that for
all $\gamma _0,\delta _0\in v(\tbinom {E} {m})\cap \Bbb R$ we have
$$
\gamma _0-\delta _0<\gamma . \tag 4
$$
Now define $\varphi :E\rightarrow \Bbb R$ by
$$
\align & \varphi (e_1):=0,\\
& \varphi (f_i):={\cases \gamma \text { if } v(\{ f_i,e_2,\hdots,e_m\} )=-\infty\\
v(B_1)-v(\{ f_i,e_2,\hdots,e_m\} ) \text { otherwise, } \endcases}\\
& \varphi (x):=-2m\cdot \gamma \text { for } x\in E\setminus \{
e_1,f_1,\hdots,f_m\} . \endalign 
$$
and put $w:=v(0,\varphi )$.
\medskip
By the definition of $\varphi $ we have
$$
v(\{ e_1,\hdots,e_m\} )\ge \varphi (x)+v(\{ x,e_2,\hdots,e_m\} ) $$
and therefore 
$$ v_{\varphi}(\{ e_1,\hdots,e_m\} )\ge v_{\varphi}(\{
x,e_2,\hdots,e_m\} )
\text { for all } x\in
E
$$
and thus $e_1\in M_w(e_2,\hdots,e_m)$.
\medskip
On the other hand, we show next that for all pairwise distinct
$x_1,\hdots,x_m\in E$ with $X:=\{ x_1,\hdots,x_m\} \ne B_2$ we have
$$
w(B_2)>w(B); \tag 5
$$
so no base $B$ with $e_1\in B$ can have maximal $v_{\varphi}$-value in contradiction
to our assumption that the greedy algorithm works for $v_{\varphi}$.
\medskip
Indeed, if $X\nsubseteq B_2\cup e_1$, then $\varphi (x_0)=-2m\cdot \gamma$
for at least one $x_0\in X$ and $\varphi (x)\le \gamma$ for all $x\in
X\setminus x_0$. This means in view of $-\gamma \le \varphi (f_i)$ for $1\le
i\le m$ also
$$
\align w(X) & =\sum \limits _{j=1}^m \varphi (x_j)+v(X)\le -(m+1)\cdot \gamma
+v(x)\\
& < -m\cdot \gamma +v(B_2)\le w(B_2). \endalign
$$
Otherwise, $X=(B_2\setminus f_i)\cup e_1$ for some $i$ with $1\le i\le m$.
If $v(f_i,e_2,\hdots,e_m)\ne -\infty $, then (3) implies
$$
w(X)=\sum \limits \Sb j=1\\ j\ne 1 \endSb ^m \varphi (f_j)+v(X)<\sum \limits
\Sb j=1\\ j\ne 1 \endSb ^m \varphi (f_j)+v(B_1)+v(b_2)-v(f_i,e_2,\hdots,e_m)
$$
and therefore
$$
w(X)<\sum\limits \Sb j=1\\ j\ne i \endSb ^m \varphi (f_j)+v(B_2)+\varphi
(f_i)=w(|B_2).
$$
Finally, if $v(f_i,e_2,\hdots,e_m)=-\infty $, then
$$
w(X)=\sum \limits \Sb j=1\\ j\ne 1 \endSb ^m \varphi (f_j)+v(X)<\sum \limits
\Sb j=1\\ j\ne i \endSb ^m \varphi (f_j)+\gamma +v(B_2)=w(B_2).
$$ 
\rightline{$\square$}
\bigskip
\bigskip
\bigskip
\centerline{{\bf References:}}
\medskip

\parindent=1truecm
\item{[DW1]} A.W.M. Dress and W. Wenzel: Grassmann-Pl\"ucker Relations and
Matroids with Coefficients. \newline
to appear in Advances in Mathematics.

\item{[DW2]} A.W.M. Dress and W. Wenzel: Valuated Matroids. \newline 
in preparation

\item{[E]} J. Edmonds: Matroids and the Greedy Algorithm. \newline
Mathematical Programming 1 (1971), 127-136.

\item{[F]} U. Faigle: The Greedy Algorithm for partially ordered Sets. \newline
Discrete Mathematics 28 (1979), 153-159.

\item{[G]} D. Gale: Optimal Assignments in an ordered Set: An Application
of Matroid Theory. \newline
Journal of Combinatorial Theory 4 (1968), 176-180.

\item{[HK]} D. Haussmann and B. Korte: K-Greedy Algorithms for Independence
Systems. \newline
Z. Operations Research 22 (1978), 219-228.

\item{[KL1]} B. Korte and L. Lov\'asz: Mathematical Structures underlying
Greedy Algorithms. \newline
Fundamentals of Computation Theory, Szeged 1981 (Springer, Berlin, 1981),
205-209.

\item{[KL2]} B. Korte, L. Lov\'asz and R. Schrader: Greedoid Theory. \newline
Algorithms and Combinatorics 4, Springer Verlag,
to appear

\item{[Kr]} J.B. Kruskal: On the shortest spanning Subgraph of a Graph and
the Travelling Salesman Problem.
Proc. Amer. Math. Soc. 7 (1956), 48-49.

\item{[R]} R. Rado: Note on Independence Functions.
Proc. London Math. Soc. 7 (1957), 300-320.

\item{[We]} D.J.A. Welsh: Matroid Theory. \newline
Academic Press London, New York, San Francisco 1976.

\item{[Wh]} H. Whitney: On the abstract Properties of Linear
Dependence.
Amer. J. Math. 57 (1935), 509-533.

\bigskip
\bigskip
\centerline{Universit\"at Bielefeld}
\centerline{Fakult\"at f\"ur Mathematik}
\centerline{Postfach 8640}
\centerline{D-4800 Bielefeld 1}
\centerline{FRG}


\bye
                                  
