The greedy algorithm as a combinatorial principle.
Ulrich Faigle · 1981
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 α = (x1, x2,...), xi ∈ P, such that (S1) for every α = (x1, x2,...) ∈ S, xi ≤ xj implies i ≤ j, (in particular: |α | ≤ |P |). (S2) for every α = (x1,..., xk) ∈ S, 0 ≤ m ≤ k, αm = (x1,..., xm) ∈ S. We define α0 = ∅ and |α0 | = 0. A (compatible) weighting of P is a function w: P → R such that x ≤ y implies w(x) ≥ w(y). (Note that w reverses the order.) w extends to a weighting of S via x∈α w(α) if ∅ � = α ∈ S, w(α) = 0 if α = ∅. The combinatorial object we seek to construct is an element α ∈ S such that w(α) is maximal. The greedy algorithm now is the following procedure: