THE GREEDY ALGORITHM AS A COMBINATORIAL PRINCIPLE

U. Faigle

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. [5]). It can either be proved directly or derived from stronger theories, e.g., the theory of flows in networks [4] or the theory of polyhedral matroids [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. [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.

The Greedy Algorithm.

Let P be a (finite) partially ordered set. A sequential family (over P) is a nonempty collection S of sequences α = (x_{1}, x_{2}, …), x_{i} ∈ P, such that

(S_{1}) for every α = (x_{1}, x_{2}, …) ∈ S, x_{i} ≤ x_{j} implies i ≤ j,

(in particular: |α| ≤ |P |). (S_{2}) for every α = (x_{1}, …, x_{k}) ∈ S, 0 ≤ m ≤ k, α_{m} = (x_{1}, …, x_{m}) ∈ S.

We define α_{0} = ∅ and |α_{0}| = 0. A (compatible) weighting of P is a function w : P → ℝ such that x ≤ y implies

w(x) ≥ w(y). (Note that w reverses the order.)

w extends to a weighting of S via

w(α) = \{ \begin{matrix}∑_{x∈α} w(α) & if ∅ ≠ α ∈ S, \\ 0 & if α = ∅. \end{matrix}

The combinatorial object we seek to construct is an element α ∈ S such that w(α) is maximal.

The greedy algorithm now is the following procedure:

Step 1: Choose x_{1} ∈ P such that w(x_{1}) is maximal under the conditions: w(x_{1}) > 0 and (x_{1}) ∈ S. If no such choice is possible, stop. Otherwise continue.

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Step k: Choose x_{k} ∈ P \{x_{1}, …, x_{k−1}} such that w(x_{k}) is maximal under the conditions: 0 < w(x_{k}) ≤ w(x_{k−1}) and (x_{1}, …, x_{k−1}, x_{k}) ∈ S. If no such choice is possible, stop. Otherwise continue.

In other words, if we list the positive elements of P in some linear order x, y, z, … so that w(x) ≥ w(y) ≥ w(z) ≥ ⋯ > 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.

Theorem [3]. The greedy algorithm produces, for every weighting of P, an optmimal sequence of S if and only if S satisfies the two conditions: (GS_{1}) for every α, β ∈ S with |α| < |β|, there is an x ∈ β and y ≤ x such that

(α, y) ∈ S. (GS_{2}) if A ⊆ B are ideals of P, p ∈ A an isthmus of S(B), then p is an isthmus of

S(A). □

Thereby we call p ∈ P an isthmus of S is p occurs in every basis of S, i.e., in every β ∈ S such that |β| = max{|α| : α ∈ S}.

Furthermore, we define for an ideal A ⊆ P,

S(A) = {α ∈ S : α ⊆ A}.

Finally, an (order) ideal of P is a subset A ⊆ P such that x ∈ A and y ≤ x imply y ∈ A.

Rank Functions.

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

(1)  for A ∈ F, r(A) = max{|α| : α ∈ S(A)},

S induces a rank function r on F, i.e., (R_{0}) r(∅) = 0, (R_{1}) for A ⊆ B ∈ F, 0 ≤ r(B) − r(A) ≤ |B − A|, (R_{2}) for A, B ∈ F, r(A ∪ B) + r(A ∩ B) ≤ r(A) + r(B). One can show that every rank function on F arises this way. Another construction to obtain rank functions is essentially due to Dilworth (see

[1]):

Say that the function f : F → ℕ is a pre-rank function if f satisfies (R_{0}) and (R_{2}) and the weaker property

(R′_{1}) for A ⊆ B ∈ F, r(A) ≤ r(B). f induces a rank function r on F via

(2)  for a ∈ F, r(A) = min{|A − B| + f(B) : B ∈ F}.

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 [2], [6]) by specializing to the case where F is the set of all vectors with integer coefficients in ℝ^{n} that are less than or equal to some non-negative vector c ∈ ℝ^{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.

Matroids.

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 matroid in terms of its rank function (see, e.g., [7]).

A subset X ⊆ P is independent if

(1′)  r(X) = |X|.

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 ⊆ P is characterized by

(2′)  for A ∈ F, f(A) ≥ |X ∩ A|.

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

If G = (U ∪ V, E) is a bipartite graph, define for every A ⊆ V,

f(A) = 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) ≥ |A| for all A ⊆ 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 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.

References

1. P. Crawley and R. P. Dilworth, Algebraic Theory of Lattices, Prentice–Hall, Englewood Cliffs, N.J., 1973.

2. J. Edmonds, Submodular functions, matroids and certain polyhedra, Proc. Int. Conf. on Combinatorics (Calgary), Gordon and Breach, New York, 1970, pp. 69–87.

3. U. Faigle, The greedy algorithm for partially ordered sets, Discrete Math. 28 (1979), 153–159.

4. L. R. Ford and D. R. Fulkerson, Flows in Networks, Princeton University Press, Princeton, 1962.

5. L. H. Harper and G.-C. Rota, Matching theory: an introduction, Adv. Probab. 1 (1971), 169–213.

6. C. J. H. McDiarmid, Rado’s theorem for polymatroids, Math. Proc. Cambridge Philos. Soc. 78 (1975), 263–281.

7. D. J. A. Welsh, Matroid Theory, Academic Press, London, 1976.

8. H. S. Wilf, A unified setting for sequencing, ranking, and selection algorithms for combinatorial objects, Adv. Math. 24 (1977), 281–291.

Fachbereich Mathematik, Technische Hochschule Darmstadt, D-6100 Darmstadt, Germany