Valuated Matroids – A new Look at the Greedy Algorithm

by

Andreas W.M. Dress and Walter Wenzel

Abstract: In this note we study a variant of the greedy algorithm for weight functions 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. Key words and phrases: Combinatorial optimization, greedy algorithm, combinatorial geometries, matroids, representation theory of matroids, valuations of fields, Grassmann-Plücker identities, greedoids.

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 greedy algorithms. More precisely, he showed that given a finite set E and a family J of subsets of E with “J ⊆ I ∈ J ⇒ J ∈ J ” we can find for any map w from E into the set ℝ_{+} of nonnegative real numbers a set I = I_{max} ∈ J with f(I) := ∑_{x∈I} f(x) ≥ f(J)

for all j ∈ J by using the greedy algorithm (that is by first choosing an element x_{1} ∈ E with {x_{1}} ∈ J and f(x_{1}) = max(f(y) | {y} ∈ J), then an element x_{2} ∈ E \ {x_{1}} with {x_{1}, x_{2}} ∈ J and f(x_{2}) = max(f(y) | {x_{1}, y} ∈ J , y ≠ x_{1}) and so on) if and only if J is the set of independent subsets of E with respect to some matroid M, defined on E. 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 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}, …, e_{m}} of M, then choose x_{1} ∈ E such that B_{1} := {x_{1}, e_{2}, …, e_{m}} is a basis, too, and f(B_{1}) ≥ f({x, e_{2}, …, e_{m}}) for all bases {x, e_{2}, …, e_{m}}. Then replace e_{2} by some x_{2} ∈ E for which B_{2}; = {x_{1}, x_{2}, e_{3}, …, e_{m}} is a basis and f(B_{2}) ≥ ({x_{1}, xe_{3}, …, e_{m}}) for all bases {x_{1}, x, e_{3}, …, e_{m}} and so on. Then we have f({x_{1}, …, x_{m}}) ≥ f(J) for all J ∈ J. One therefore may ask for an arbitrary map v from the set \binom{E}{m} of all m-subsets of E into ℝ ∪ {−∞} for conditions under which the corresponding algorithm of replacing the elements e_{1}, …, e_{m} of some m-subset {e_{1}, …, e_{m}} of E with v({e_{1}, …, e_{m}}) ≠ −∞ consecutively by some x_{1}, …, x_{m} in a locally optimal or greedy fashion, the resulting set {x_{1}, …, x_{m}} satisfies v({x_{1}, …, x_{m}}) ≥ v({y_{1}, …, y_{m}}) for all m-subsets {y_{1}, …, y_{m}} of E.

This question has a surprisingly simple answer if, as suggested by D. Gale’s result, one modifies it as follows: Given some v : \binom{E}{m} → ℝ ∪ \{−∞\} with v(\binom{E}{m}) ≠ \{−∞\}, find necessary and sufficient conditions for v such that for all maps φ : E → ℝ the maximal value of v_{φ} : \binom{E}{m} → ℝ ∪ \{−∞\} given by

v_{φ}({e_{1}, …, e_{m}}) := v({e_{1}, …, e_{m}}) + φ(e_{1}) + … + φ(e_{m})

can be found by the greedy algorithm, explained above. As we will show, this is possible for all φ : E → ℝ if and only if the following variant of the matroid exchange property holds: (V1) For all B_{1}, B_{2} ∈ \binom{E}{m} and e ∈ B_{1} \ B_{2} there exists some f ∈ B_{2} \ B_{1} with

v(B_{1}) + v(B_{2}) ≤ v((B_{1} \ {e}) ∪ {f}) + v((B_{2} \ {f}) ∪ {e}).

Interesting examples of maps v : \binom{E}{m} → ℝ ∪ \{−∞\}, 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]): If E is a finite subset of ℚ^{m} which spans ℚ^{m}, then the Grassmann-Plücker relations imply that for a given prime number p the map v_{p} : \binom{E}{m} → ℝ ∪ \{−∞\} defined by

v_{p}(\{e_{1}, …, e_{m}\}) := \{ \begin{matrix}−∞ & if det(e_{1}, …, e_{m}) = 0 \\ n & if det(e_{1}, …, e_{m}) = p^{−n} · \frac{a}{b} \\ & with n ∈ ℤ, a, b ∈ ℤ \ p · ℤ \end{matrix}

satisfies our condition. Hence, as an application of our result, one could compute a basis e_{1}, …, e_{m} of ℚ^{m}, contained in E, for which the p-part of det(e_{1}, …, e_{m}) is as small as possible, by the above greedy algorithm.

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. [...]).

In the sequel we assume that E is some finite set and m ∈ ℕ satisfies m ≤ #E.

For a map v : \binom{E}{m} → ℝ ∪ \{−∞\} we put

v(e_{1}, …, e_{m}) := \{ \begin{matrix}v(\{e_{1}, …, e_{m}\}) & if \{e_{1}, …, e_{m}\} ∈ \binom{E}{m} \\ −∞ & otherwise . \end{matrix}

Definition 1: A valuated matroid of rank m with values in ℝ, is a pair (E, v), consisting of a finite set E with #E ≥ m together with a map v : \binom{E}{m} → ℝ ∪ \{−∞\} satisfying (V1) and

(V0)  there exists some B ∈ \binom{E}{m} with v(B) ≠ −∞.

An m-set B ∈ \binom{E}{m} is called a basis of the valuated matroid (E, v), if v(B) ≠ −∞.

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 \binom{E}{m} into ℝ∪\{−∞\} which satisfies (V0) and (V1) is called a valuation of M, if for all B ∈ \binom{E}{m} one has v(B) ≠ −∞ if and only if B is a basis of M.

ii) A valuation v : \binom{E}{m} → ℝ ∪ \{−∞\} is called trivial, if there exists some α ∈ ℝ with v(B) ∈ \{α, −∞\} for all B ∈ \binom{E}{m}.

Every combinatorial geometry M of rank m, defined on E, has a trivial valuation v : \binom{E}{m} → ℝ ∪ \{−∞\}, namely

v(B) := \{ \begin{matrix}0 & if B is a base of M \\ −∞ & otherwise . \end{matrix}

This is nothing but a reformulation of the strong exchange property for bases of M.

Definition 2: Assume v : \binom{E}{m} → ℝ ∪ \{−∞\} is some map with v(B) ≠ −∞ for at least one B ∈ \binom{E}{m}. The greedy algorithm runs as follows:

Step 0 : Choose some e_{1}, …, e_{m} ∈ E with v({e_{1}, …, e_{m}}) ≠ −∞.

Step k(1 ≤ k ≤ m) : Assume that x_{1}, …, x_{k−1} ∈ E are already determined and choose some x_{k} ∈ E such that

v({x_{1}, …, x_{k}, e_{k+1}, …, e_{m}}) ≥ v({x_{1}, …, x_{k−1}, x, e_{k+1}, …, e_{m}})

for all x ∈ E.

We say that the greedy algorithm works for v if for all starting sequences e_{1}, …, e_{m} ∈ E with v({e_{1}, …, e_{m}}) ≠ −∞ and all permitted choices of the x_{1}, …, x_{m} one has v(\{x_{1}, …, x_{m}\}) ≥ v(B) for all B ∈ \binom{E}{m} in which case v is called admissible.

For e_{1}, …, e_{m−1} ∈ E put

M_{v}(e_{1}, …, e_{m−1})
:= {x ∈ E | v(e_{1}, …, e_{m−1}, x) ≥ v(e_{1}, …, e_{m−1}, y) for all y ∈ E}.

Obviously, v is admissible if and only if for all e_{1}, …, e_{m} ∈ E with v(e_{1}, …, e_{m}) ≠ −∞ and all x_{1}, …, x_{m} ∈ E with

x_{i} ∈ M_{v}(x_{1}, …, x_{i−1}, e_{i+1}, …, e_{m}) for 1 ≤ i ≤ m

we have v(x_{1}, …, x_{m}) ≥ v(y_{1}, …, y_{m}) for all y_{1}, …, y_{m} ∈ E.

Definition 3: Two maps v, w : \binom{E}{m} → ℝ ∪ \{−∞\} are called projectively equivalent, if there exists some α ∈ ℝ and some map φ : E → ℝ such that

w(e − 1, …, e_{m}) = α + ∑_{i=1}^{m} φ(e_{i}) + v(e_{1}, …, e_{m}) for all e_{1}, …, e_{m} ∈ E.

If this is the case, we write w := v(α, φ).

Remark: If v : \binom{E}{m} → ℝ ∪ \{−∞\} is a valuation of some combinatorial geometry M, then it is clear that v(α, φ) is also a valuation of M for all α ∈ ℝ and all maps φ : E → ℝ.

Now we can show

Theorem: Assume E is a finite set with #E ≥ m and v : \binom{E}{m} → ℝ ∪ \{−∞\} is some map satisfying (V0). Then (E, v) is a valuated matroid, if and only if the greedy algorithm works for v_{φ} for all α ∈ ℝ and all maps φ : E → ℝ.

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.

Assume e_{1}, …, e_{m} ∈ E with v({e_{1}, …, e_{m}}) ≠ 0 and x_{1}, …, x_{m} ∈ E such that x_{i} ∈ M_{v}(x_{1}, …, x_{i−1}, e_{i+1}, …, e_{m}) for 1 ≤ i ≤ m. Put B_{0} := {x_{1}, …, x_{m}}. We must prove

(1)  v(B) ≤ v(B_{0}) for all B ∈ \binom{E}{m}.

At first we show

(2)  v((B_{0} \ x_{j}) ∪ x) ≤ v(B_{0}) for 1 ≤ j ≤ m and all x ∈ E.

By our assumption (2) is clear for j = m.

To prove (2) for 1 ≤ j ≤ m − 1 we may assume by induction that

(2a)  v((B_{0} \ {x_{j}, x_{m}}) ∪ {x, e_{m}}) ≤ v((B_{0} \ x_{m}) ∪ e_{m}) for all x ∈ E,

because v′ : \binom{E\e_{m}}{m−1} → ℝ ∪ \{−∞\} defined by

v′(A) := v(A ∪ e_{m}) (A ∈ \binom{E\e_{m}}{m})

is obviously a valuation of the contraction M′ := M/{e_{m}} of rank m − 1.

Now assume v((B_{0} \ x_{j}) ∪ x) ≠ −∞ for some fixed j with 1 ≤ j ≤ m − 1 and some fixed x ∈ E. Consider the bases B_{1} := (B_{0} \ x_{m}) ∪ e_{m} and B_{2} := (B_{0} \ x_{j}) ∪ x of M.

(2) clearly holds in case x_{j} = x. Otherwise we have x_{j} ∈ B_{1} \ B_{2}. Thus there exists e ∈ B_{2} \ B_{1} ⊆ {x_{m}, x} with

v(B_{1}) + v(B_{2}) ≤ v((B_{1} \ x_{j}) ∪ e) + v((B_{2} \ e) ∪ x_{j}).

But (2a) yields v((B_{1} \ x_{j}) ∪ e) ≤ v(B_{1}) and thus

(2b)  v(B_{2}) ≤ ((b_{2} \ e) ∪ x_{j}).

Furthermore, we have {x_{1}, …, x_{m−1}} ⊆ (B_{2} \ e) ∪ x_{j}, and thus our choice of x_{m} implies

(2c)  v((B_{2} \ e) ∪ x_{j}) ≤ v(B).

(2) follows now from (2b) and (2c). Now we derive (1) from (2) by induction on n := #({y_{1}, …, y_{m}} \ {x_{1}, …, x_{m}}). The cases n = 0 and v(y_{1}, …, y_{m}) = 0 are trivial, while for n = 1 we are done by (2). Now assume 2 ≤ n ≤ m, say, #{y_{1}, …, y_{n}, x_{1}, …, x_{m}} = n + m and y_{k} = x_{k} for n + 1 ≤ k ≤ m. Then by (V1), (2) and our induction hypothesis there exists i with 1 ≤ i ≤ n and

v({y_{1}, …, y_{n}, x_{n+1}, …, x_{m}}) + v(B_{0})
≤v({x_{i}, y_{2}, …, y_{n}, x_{n+1}, …, x_{m}}) + v((B_{0} \ x_{i}) ∪ y_{1})
≤2 · v(B_{0}).

Since v(B_{0}) ≥ v({e_{1}, …, e_{m}}) > −∞, this means

v(y_{1}, …, y_{n}, x_{n+1}, …, x_{m}) ≤ v(B_{0}).

Now assume that, vice versa, v_{φ} is admissible for all α ∈ ℝ and all maps φ : E → ℝ. We have to show that v satisfies (V1). Otherwise assume e_{1}, …, e_{m}, f_{1}, …, f_{m} ∈ E are such that for B_{1} := {e_{1}, …, e_{m}} and B_{2} := {f_{1}, …, f_{m}} we have

(3)  v(B_{1}) + v(B_{2}) > v((B_{2} \ f_{i}) ∪ e_{1}) + v((B_{1} \ e_{1}) ∪ f_{i})

for all i with 1 ≤ i ≤ m. Then we must have e_{1} ∉ B_{2} and v(B_{2}) ≠ −∞. Since E is finite, we can choose some γ ∈ ℝ such that for all γ_{0}, δ_{0} ∈ v(\binom{E}{m}) ∩ ℝ we have

(4)  γ_{0} − δ_{0} < γ.

Now define φ : E → ℝ by

φ(e_{1}) := 0,

φ(f_{i}) := \{ \begin{matrix}γ if v(\{f_{i}, e_{2}, …, e_{m}\}) = −∞ \\ v(B_{1}) − v(\{f_{i}, e_{2}, …, e_{m}\}) otherwise, \end{matrix}

φ(x) := −2m · γ for x ∈ E \ {e_{1}, f_{1}, …, f_{m}}.

and put w := v(0, φ). By the definition of φ we have

v({e_{1}, …, e_{m}}) ≥ φ(x) + v({x, e_{2}, …, e_{m}})

and therefore

v_{φ}({e_{1}, …, e_{m}}) ≥ v_{φ}({x, e_{2}, …, e_{m}}) for all x ∈ E

and thus e_{1} ∈ M_{w}(e_{2}, …, e_{m}).

On the other hand, we show next that for all pairwise distinct x_{1}, …, x_{m} ∈ E with X := {x_{1}, …, x_{m}} ≠ B_{2} we have

(5)  w(B_{2}) > w(B);

so no base B with e_{1} ∈ B can have maximal v_{φ}-value in contradiction to our assumption that the greedy algorithm works for v_{φ}.

Indeed, if X ⊈ B_{2} ∪ e_{1}, then φ(x_{0}) = −2m · γ for at least one x_{0} ∈ X and φ(x) ≤ γ for all x ∈ X \ x_{0}. This means in view of −γ ≤ φ(f_{i}) for 1 ≤ i ≤ m also

w(X) = ∑_{j=1}^{m} φ(x_{j}) + v(X) ≤ −(m + 1) · γ + v(x)
< −m · γ + v(B_{2}) ≤ w(B_{2}).

Otherwise, X = (B_{2} \ f_{i}) ∪ e_{1} for some i with 1 ≤ i ≤ m. If v(f_{i}, e_{2}, …, e_{m}) ≠ −∞, then (3) implies

w(X) = ∑_{\begin{matrix}j=1 \\ j≠1 \end{matrix}}^{m} φ(f_{j}) + v(X) < ∑_{\begin{matrix}j=1 \\ j≠1 \end{matrix}}^{m} φ(f_{j}) + v(B_{1}) + v(b_{2}) − v(f_{i}, e_{2}, …, e_{m})

and therefore

w(X) < ∑_{\begin{matrix}j=1 \\ j≠i \end{matrix}}^{m} φ(f_{j}) + v(B_{2}) + φ(f_{i}) = w(|B_{2}).

Finally, if v(f_{i}, e_{2}, …, e_{m}) = −∞, then

w(X) = ∑_{\begin{matrix}j=1 \\ j≠1 \end{matrix}}^{m} φ(f_{j}) + v(X) < ∑_{\begin{matrix}j=1 \\ j≠i \end{matrix}}^{m} φ(f_{j}) + γ + v(B_{2}) = w(B_{2}).

□

References:

[DW1] A.W.M. Dress and W. Wenzel: Grassmann-Plücker Relations and Matroids with Coefficients. to appear in Advances in Mathematics.

[DW2] A.W.M. Dress and W. Wenzel: Valuated Matroids.

in preparation

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

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

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

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

[KL1] B. Korte and L. Lovász: Mathematical Structures underlying Greedy Algorithms. Fundamentals of Computation Theory, Szeged 1981 (Springer, Berlin, 1981), 205-209.

[KL2] B. Korte, L. Lovász and R. Schrader: Greedoid Theory.

Algorithms and Combinatorics 4, Springer Verlag, to appear

[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.

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

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

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

Universität Bielefeld Fakultät für Mathematik Postfach 8640 D-4800 Bielefeld 1 FRG