[Tutorial] Greedoids: a formal way to look at families of greedily-solvable prob...

[Tutorial] Greedoids: a formal way to look at families of greedily-solvable problems

Disclaimer: This is not an introduction to greedy algorithms; rather, it is only a way to formalize and internalize certain patterns that crop up while solving problems that can be solved using a greedy algorithm.

Note for beginners: If you're uncomfortable with how to prove the correctness of greedy algorithms, I would refer you to this tutorial that describes two common ways of proving correctness — "greedy stays ahead" and "exchange arguments". For examples of such arguments, I would recommend trying to prove the correctness of standard greedy algorithms (such as choosing events to maximize number of non-overlapping events, Kruskal's algorithm, binary representation of an integer) using these methods, and using your favourite search engine to look up more examples.

Have you ever wondered why greedy algorithms sometimes magically seem to work? Or find them unintuitive in a mathematical sense? This post is meant to be an introduction to a mathematical structure called a greedoid (developed in the 1980s, but with certain errors that were corrected as recently as 2021), that captures some intuition behind greedy algorithms and provides a fresh perspective on them.

The idea behind this blog is to abstract out commonly occurring patterns into a single structure, which can be focused upon and studied extensively. This helps by making it easy to recognize such arguments in many situations, especially when you're not explicitly looking for them. Note that this blog is in no way a comprehensive collection of all results about greedoids; for a more comprehensive treatment, I would refer you to the references as well as your favourite search engine. If there is something unclear in this blog, please let me know in the comments.

To get an idea as to how wide a variety of concepts it is connected to is, greedoids come up in BFS, Dijkstra's algorithm, Prim's algorithm, Kruskal's algorithm, Blossom's algorithm, ear decomposition of graphs, posets, machine scheduling, convex hulls, linear algebra and so on, some of which we shall discuss in this blog.

Note that we will mainly focus on intuition and results, and not focus on proofs of these properties, because they tend to become quite involved, and there is probably not enough space to discuss these otherwise. However, we will give sketches of proofs of properties that are quite important in developing an intuition for greedoids.

Table of contents

1. Motivation and definition
   • Unordered version of conditions on optimality
   • Weaker conditions on optimality of the greedy algorithm
2. Some examples
   • Interval greedoids
   • Matroids
   • Antimatroids
   • Other greedoids
3. Constructing more greedoids
   • From matroids
   • From antimatroids
   • From greedoids
4. Some random facts about greedoids
5. References and further reading

Motivation and definition

We will take an approach in an order that is different from most treatments of greedoids (which throw a definition at you), and try to build up to the structure that a greedoid provides us.

How does a usual greedy algorithm look like? Initially, we have made no decisions. Then we perform a sequence of steps. After each step, we have a string of decisions that we have taken (for instance, picking some element and adding it to a set). We also want a set of final choices (so we can't extend beyond those choices).

To make this concept precise, we define the following:

1. A ground set is any set. We usually interpret this as a set of incremental decisions that can be made.
2. A language is any set of finite sequences (or words) of elements coming from the ground set. We interpret a language as a set of possible sequences of decisions we can take in the greedy algorithm.
3. A simple language is any language where the sequences don't have repeated elements. This definition is motivated from the fact that we don't take a decision more than once.
4. A hereditary language is any language on a ground set satisfying the following two conditions:
   • For any , every prefix of is also in . This definition is motivated from the fact that we want to capture a sense of time/causality in our sequence of decisions. That is, if we have a sequence of decisions, we must have arrived at it from the just-smaller prefix of decisions.
5. A basic word in is any such that there is no element in such that extended by that element (denoted by or ) is in . This is motivated from the fact that we want to have some ending states at the end of the greedy algorithm.

We can now rephrase the optimization problems that a large set of greedy algorithms try to solve in the following terms:

• Consider a simple hereditary language on the ground set , and a function . Now maximize where is a basic word of .

A (certain quite general type of) greedy algorithm looks something like this:

• Initially there are no decisions taken.
• At step , when the decisions have already been taken, pick an such that , and this choice of maximizes over all valid choices of . If there is no such , terminate the algorithm.

Of course, taking arbitrary doesn't make any sense, so we limit to the following kinds of functions (we shall relax these conditions later, so that we can reason about a larger variety of problems):

1. If at a certain point, a decision is optimal, then it will also be optimal at a later stage. That is, if is chosen when the prefix was , then for a prefix , we have for all valid ( can be empty, is a decision).
2. It is optimal to pick sooner than later. That is, if is chosen when the prefix was , then we must have for all valid ( can be empty, is a decision).

To this end, we define greedoids as follows:

A greedoid is a simple hereditary language on a ground set that satisfies an "exchange" property of the following form:

• If satisfy , then there is a decision in that we can append to , so that the resulting word is also in .

This extra condition is crucial for us to be able to prove the optimality of greedy solutions using an exchange argument (the usual exchange argument that people apply when proving the correctness of greedy algorithms).

One notable result is that by this extra condition, all basic words in have the same length. This might seem like a major downgrade from the kind of generality we were going for, but it still handles a lot of cases and gives us nice properties to work with.

It turns out that greedoids have the following equivalent definitions which will be useful later on (we omit the proofs, since they are quite easy):

1. Let a set variant of the greedoid be defined as follows: a pair of a ground set and a family of its subsets , such that and for any with , there exists an such that . Then the original definition of a greedoid and this definition of a set variant are equivalent, in the sense that for any such , there is exactly one simple hereditary language such that the set of set of decisions in a word for each word in is precisely . (That is, when we replace sequences in with an unordered version, the resulting set of unordered sets is ).
2. We can replace the second condition in the definition of the set variant by the condition that all maximal sets have the same cardinality. Maximal sets are defined as sets such that the set formed after adding another element to them is not in .

There is also a set analogue for simple hereditary languages: and for each , we have an element such that . The intuition remains the same. Note that again, we don't need this to hold for all , but at least one .

But why do we care about greedoids at all? The answer lies in the following informally-stated two-part theorem:

Theorem 1:

1. If is a greedoid on , and satisfies the conditions mentioned earlier, then the greedy algorithm gives the correct answer.
2. If the greedy algorithm gives the correct answer for all satisfying the conditions mentioned earlier, and if has the same length for all its basic words, then is a greedoid on .

Note that the definition of greedoid doesn't depend on in any way, so it can be studied as a combinatorial structure in its own right — this leads to quite non-trivial results at times. However, when we think of them in the greedy sense, we almost always have an associated .

In a lot of cases, has a much simpler (and restrictive) structure, for instance, having a positive and additive weight function (which is defined on each element). In that case, the following algorithm works for matroids (special cases of greedoids): sort elements in descending order of their weight, and pick an element iff adding it to the set of current choices is still in the matroid.

Unordered version of conditions on optimality

Usually, is not defined on a sequence of steps, but on the set of choices you have made. However, in the general case, the "natural" relaxation from the ordered version to the unordered version of greedoids fails (both in being equivalent and in giving the optimal answer). In fact, this error was present in the original publications (since 1981) and was corrected fairly recently in 2021. For a more detailed discussion (and the proofs of the following few theorems), please refer to , which we shall closely follow.

We shall start out with some special cases:

Theorem 2: Consider a greedoid (unordered) on a ground set . Suppose is a utility function from to , so that the weight of a set of decisions is additive over its elements. Then the greedy algorithm gives an optimal solution iff the following is true:

• If and is an unordered basic word (i.e., maximal set) in such that and , then there is a such that and is also a maximal set.

The following theorem generalizes the sufficiency:

Theorem 3: Consider a greedoid (unordered) on a ground set and . The greedy algorithm gives an optimal solution if (and not iff) the following is true:

• If for some and being an unordered basic word (i.e., maximal set) in such that and , it holds that for all valid , then there is a such that and is also a maximal set and .

This theorem can be used to show optimality of Prim's algorithm on its corresponding greedoid.

This theorem can also be derived from theorem 6 that we shall mention later on.

Remember that we mentioned that the original claim in the 1981 paper about greedoids was false? It turns out that the claim is true about a certain type of greedoids, called local forest greedoids. Since it is not so relevant to our discussion, we're going to spoiler it to avoid impairing the readability of what follows.

Weaker conditions on optimality of the greedy algorithm

As we had mentioned earlier, the constraints on while motivating the definition of a greedoid (ordered) are quite stringent, and they might not hold in a lot of cases. Here, we work upon reducing the set of constraints (which will also have implications on theorem 3 earlier).

Theorem 6: Let be a greedoid on a ground set , and be an objective function that satisfies the following condition:

• If such that for every valid and is a basic word, then there exists a basic word such that .

Then the greedy algorithm gives an optimal solution.

The proof is quite easy, and goes by way of contradiction. There is a special case of the above theorem (that needs some care to prove), which is applicable in a lot of cases. It turns out that it corresponds to the last part of the proof sketch of Theorem 1, so maybe it's not such a bad idea to read it again.

Some examples

The main point of adding examples at this point is to showcase the kinds of greedoids that exist in the wild and some of their properties, so that it becomes easy to recognize these structures. I have added the examples in spoiler tags, just to make navigation easier. Some of these examples will make more sense after reading the section on how to construct greedoids.

While going through these examples, I encourage you to find some examples of cost functions that correspond to greedy optimality, so that you can recognize them in the future. Discussing them in the comments can be a great idea too. For a slightly larger set of examples, please refer to Wikipedia and the references.

When appropriate, we will also point out greedy algorithms that are associated with these structures.

Interval greedoids

These are greedoids that satisfy the local union property (as introduced in the section of local forest greedoids). Equivalently, they are also defined as greedoids where for every with , if for some , then .

Some examples are:

1. All local forest greedoids.
2. Matroids (to be introduced later).
3. Anti-matroids (to be introduced later).

Matroids

Matroids are greedoids that satisfy a stronger property than the interval property for interval greedoids, by removing the lower bounds. More precisely, a matroid is a greedoid that satisfies the following property:

• For every with , if for some , then .

Equivalently, they are greedoids where in the unordered version, for each , and for all (not at least one) we have . In other words, they are downwards closed. In such a context, elements of are also called independent sets.

Intuitively, they try to capture some concept of independence. In fact, matroids came up from linear algebra and graph theory, and greedoids were a generalization of them when people realized that matroids are too restrictive, and downwards-closedness is not really important in the context of greedy algorithms. The examples will make this notion clearer.

Note that for matroids, it is sufficient to define a basis (the set of maximal sets in ), and downwards closedness handles the rest for us.

Matroids have a much vaster theory compared to greedoids, due to being studied for quite a long time and being more popular in the research community. Since this is a blog only on greedy algorithms, we will refrain from diving into matroid theory in too much detail. Interested readers can go through the references for more.

Some examples of matroids are as follows.

Antimatroids

Antimatroids are greedoids that satisfy a stronger property than the interval property for interval greedoids, by removing the upper bounds. More precisely, an antimatroid is a greedoid that satisfies the following property:

• For every with , if for some , then .

Unlike matroids, this does not necessarily imply upward closure, but it does imply closure under unions (which is another way to define antimatroids).

Another definition of antimatroids that is in terms of languages (and gives some intuition about their structure) calls a simple hereditary language over a ground set an antimatroid iff the following two conditions hold:

1. Every element of the ground set must appear in a word in the language.
2. The exchange property holds for any two words such that has an element not in , rather than only restricting it to .

Using this, we note that the basic words are all permutations of the ground set.

Another piece of intuition (derived from the above definition) that helps with antimatroids is the fact that when we try constructing sets in an antimatroid, we keep adding elements to a set, and once we can add an element, we can add it any time after that.

It also makes sense to talk about antimatroids in the context of convex geometries. To understand the intuition behind this, we take the example of a special case of what is called a shelling antimatroid. Let's consider a finite set of points in the 2D plane. At each step, remove a point from the convex hull of the remaining points. The set of points at any point in this process clearly forms an antimatroid by the above intuition. In fact, if instead of 2D, we embed the ground set in a space with a high enough dimension, we can get an antimatroid isomorphic to the given matroid!

What is so special about convexity here? Turns out we can use some sort of "anti-exchange" rule to define convex geometries in the following manner. It will roughly correspond to this fact: if a point is in the convex hull of a set and a point , then is outside the convex hull of and .

Let's consider a set system closed under intersection, which has both the ground set and empty set in it. Any subset of the ground set (doesn't matter whether it is in the system or not) has a smallest superset in such a set system (and it is the smallest set from the system that contains the subset). Let's call this mapping from the subset to its corresponding smallest superset in the system . Then we have the following properties:

Now for such a set system, it is called a convex geometry if the following "anti-exchange" property holds:

• If some distinct , but , then .

Intuitively, consider as a convex hull operator. Then the anti-exchange property simply means that if is in the convex hull of and , then is outside the convex hull of and .

Now it turns out that the complements of all sets in an antimatroid form a convex geometry! This is not too hard to prove.

We shall now give some examples of antimatroids.

Other greedoids

Now that we got a few special types of greedoids out of the way, we shall look at some more greedoids.

Constructing more greedoids

Note that some constructions from polymatroids/matroids etc. were already mentioned in the section on examples, so we will focus on the ones that were not.

From matroids

From antimatroids

From greedoids

Some random facts about greedoids

This is a collection of interesting facts about greedoids that just don't seem to fit in the above sections, but are important enough not to be ignored. Of course, with every important construction or idea, there are a lot of facts that lead to a combinatorial explosion of the kinds of facts we can derive about anything, so what we discussed above is way too incomplete to be a comprehensive introduction. It'll hopefully evolve over time too, so I'm open to suggestions regarding this section.

• You can construct Tutte polynomials for greedoids, just like you can for matroids.
• We can characterize greedoids into matroids, antimatroids, and none of these in terms of having certain kinds of greedoid minors.
• Antimatroids are very closely related to lattices, and in general we can reason about greedoids by their associated poset flats too.

References and further reading

1. Dávid Szeszlér (2021), Sufficient conditions for the optimality of the greedy algorithm in greedoids.
2. Bernhard Korte, Laszlo Lovasz, Rainer Schrader (1991), Greedoids
3. Matroid intersection in simple words
4. Goecke, Korte, Lovasz (1986), Examples and algorithmic properties of greedoids
5. Bernhard Korte, Laszlo Lovasz (1988), Intersection of matroids and antimatroids
6. Brenda L Dietrich (1987), Matroids and antimatroids — a survey

Lastly, since this is a huge blog, some mistakes might have crept in. If you find any, please let me know!