# Does every greedy algorithm have matroid structure?

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.

• Dijkstra's algorithm is often considered a greedy algorithm (e.g. see Section 4.4 of "Algorithm Design" by Kleinberg and Tardos). I don't know of a matroid interpretation of single-source shortest paths. – Neal Young Oct 25 '19 at 16:28
• Partitioning a set of real intervals into a minimum number of pairwise-disjoint subsets has a natural greedy algorithm (enumerate intervals by start time, for each add it to an existing subset if possible, else start a new subset; see Chapter 4 of Kleinberg and Tardos). Can this problem be understood as a matroid? – Neal Young Nov 5 '19 at 18:10

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.

• Can you explain what is their definition of a greedy algorithm? – Kaveh Mar 6 '14 at 23:59
• Expanded my answer to explain what their formalism is. – Magnus Lie Hetland Mar 8 '14 at 20:59

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.

• A formal definition is not required if we agree on some property of the class of greedy algorithms. If, for instance, we agreed that every greedy algorithm has (a formally defined) property P, and we showed that every algorithm that satisfies P can be defined on a matroid, that would give a positive answer to the OP's question. Similarly, if we agreed that a certain algorithm is greedy and we showed it can't be the greedy algorithm of a matroid, that would yield a negative answer. – Detached Laconian Apr 23 '18 at 17:07

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.

• thanks, i had my suspicions but was not sure. So after all we have to search for greedy algorithm even if matroid structure does not exist. – user3373748 Mar 4 '14 at 10:17
• @user3373748 I usually just look for a dynamic program. Greedy is a degenerate DP. – David Eisenstat Mar 4 '14 at 14:42
• (Not to be picky, but there are no 1- or 2-euro notes; you may want to change your set of values to {5, 10, 20, 50, 100, 200} or rephrase ;-)) – Anthony Labarre Mar 5 '14 at 6:53
• Note that the described coin-changing algorithm works for {1,2,5,10} but may not compute optimal results for other values. Example: With {1,3,4} the optimal solution for 6 would be [3,3] but the algorithm would return [4,1,1]. – Socowi Mar 24 '18 at 18:11
• There is a matroid structure for the coin-change problem - gauss.ececs.uc.edu/Courses/C671/html/Homework/hw5_sol.html – Tushant Mittal May 15 '19 at 15:42