Activity Selection and Matroid Theory

Question

Many people on different articles suggests that if an optimization problem has a greedy solution, the underlying structure must have matroid property.

I was trying to understand this. So far, I was able to prove that for,

1. Maximum sum of m integers among n integer.
2. Minimum spanning tree.

However, The classical greedy algorithm Activity Selection seems to fail having both independence and base exchange property.

Let, E = {1-3, 2-4, 3-5, 4-6, 5-7}

Now, Take two independent set, I = {2-4, 4-6} and J = {1-3, 3-5, 5-7}

There is no activity in J which can extend I. Which fails the independence exchange property of matroid, if I understood it correctly. Thus, it is not matroid and shouldn't have a greedy algorithms. But this problem has a greedy solution.

Where am I wrong?

Answer 1

Suppose that $\mathcal{F}$ is a nonempty collection of subsets of a finite set $U$ satisfying the following axiom:

If $A \in \mathcal{F}$ and $B \subseteq A$ then $B \in \mathcal{F}$.

Consider the following algorithm, which gets as input a weight function $w\colon U \to \mathbb{R}_+$ (here $\mathbb{R}_+$ consists of all positive reals):

1. Set $S \gets \emptyset$.

2. While there exists an element $x \notin S$ such that $S \cup \{x\} \in \mathcal{F}$:

   • Let $x$ be an element of maximum weight among $\{ x : x \notin S \text{ and } S \cup \{x\} \in \mathcal{F} \}$.
   • Set $S \gets S \cup \{x\}$.

3. Return $S$.

We say that the algorithm is valid for $w$ if it returns a set $S$ maximizing $\sum_{x \in S} w(x)$ among all $S \in \mathcal{F}$.

Theorem. The algorithm is valid for all $w\colon U \to \mathbb{R}^+$ iff $\mathcal{F}$ is a matroid.

You can find the proof of this theorem in lecture notes and in textbooks.

The algorithm given above is a specific greedy algorithm. This specific greedy algorithm is optimal if and only if the set system is a matroid. However, the (informal) notion of greedy algorithms encompasses more than just this specific algorithm. The theorem above doesn't apply to these algorithms.

In the two good examples you consider, the corresponding greedy algorithms (or at least one of their variants) are instances of the algorithm above. The same isn't true for the algorithm for your bad example.

For a formalized notion of "greedy-like" algorithms, consult (Incremental) priority algorithms by Borodin, Nielsen, and Rackoff. You can see that is is much more general than the simple algorithm stated above.

Another relevant notion is that of greedoid, for which a theorem similar to the one stated above does hold (see Wikipedia for details).