Does every greedy algorithm have matroid structure?

Question

It is well established that for every matroid $M$ and any weight function $w$, there exits an algorithm $\mbox{GreedyBasis}(M,w)$ which returns a maximum weight basis of $M$. So, is the reverse direction also true? That is, if there is some greedy algorithm, then there must be some matroid structure also.

Answer 1

Actually, the complete and general description of a problem that can be solved by a greedy algorithm is a matroid embedding, which generalizes both the concept of a matroid and that of a greedoid. The answer is no—a problem solvable by a greedy algorithm need not have a matroid structure, but it will have the structure of a matroid embedding (which is, alas, much more complicated).

A mental model for some of this could be finding minimum spanning trees. The structure used by Kruskal's algorithm is a matroid, but that used by Prim's algorithm (which requires a start node) is not. (It is, however, a greedoid—and a matroid embedding.)

Helman et al. (1993), in their paper An Exact Characterization of Greedy Structures define their notion of a greedy algorithm in terms of set systems, which is the same formalism that is used for matroids and greedoids. A set system $(S,\mathcal{C})$ consists of a set $S$ and a collection $\mathcal{C}$ of subsets of $S$, the so-called feasible sets. A basis for the set system is a maximal feasible set, that is, a set that is feasible but not contained in any other feasible set. An objective function $f:2^S\rightarrow\mathbb{R}$ associates each subset of $S$ with a value. An optimization problem, in this formalism, consists in finding a basis of maximum objective value for a given set system and objective function.

The greedy algorithm, defined in terms of this formalism, is quite simple: You start with the empty set, and successively add a single element until you reach a basis, always ensuring that (i) your set is feasible at each step, and (ii) the element you add maximizes the objective function of the resulting result, wrt. all the alternative elements you could have added. (That is, conceptually, you try adding all feasible alternatives, and choose the one yielding the highest objective value.)

You could, perhaps, argue that there might be other forms of greedy algorithm, but there are several textbooks on algorithms and combinatorial optimization that describe this set-system based algorithm as the greedy algorithm. That doesn't prevent you from describing something that doesn't fit, but could still be called greedy, I suppose. (Still, this does cover anything that could potentially have a matroid structure, for example, though it is much more general.)

What Helman et al. do is that they describe when this algorithm will work. More specifically:

1. They show that for linear objective functions (where the objective value is the sum of element weights), the greedy algorithm will work exactly on the structure they define as a matroid embedding;

2. They give a similar characterization for so-called bottleneck objectives (where the objective value of a set is equal to the minimum over the individual element weights); and

3. They give an exact characterization of which objective functions (beyond linear ones) are optimized by the greedy algorithm on matroid embeddings.

Answer 2

Greedy algorithm is not a formally defined concept. There are various models trying to capture this intuitive notion but there is no consensus on what is a greedy algorithm. Unless you specify a formal definition of what you mean by a greedy algorithm the question cannot be answered as yes or no.

There is a generalization of matroids called greedoid which is inspired by greedy algorithms what you may want to look at.

Answer 3

Consider following problems: COIN-CHAINING EURO: Given infinite amount of 1,2,5,10 euro notes, pay X euro using as few notes as possible. This can be solved by using greedy algorithm, which takes largest note possible. But there is no matroid structure in this problem.

HOLE COVERAGE: There are holes in positions x_1, x_2, ..., x_n. You have patch of length 10 cm. Patch the holes using as few patches as possible. Again this can be solved in greedy fashion (just put patch as right as possible), but there is no matroid structure.