Summary: The authors present exact characterizations of structures on which the greedy algorithm produces optimal solutions. Our characterization, which are called matroid embeddings, complete the partial characterizations of

*R. Rado* [Note on independent functions, Proc. London Math. Soc., III. Ser. 7, 300-320 (1957;

Zbl 0083.023)],

*D. Gale* [Optimal assignments in an ordered set, J. Comb. Theory 4, 176-180 (1968;

Zbl 0197.008)], and

*J. Edmonds* [Matroids and the greedy algorithm, Math. Programming 1, 127-136 (1971;

Zbl 0253.90027)] (matroids), and of

*B. Korte* and

*L. Lovasz* [Greedoids and linear object functions, SIAM J. Algebraic Discrete Methods 5, 229-238 (1984;

Zbl 0538.05027)] and [Mathematical structures underlying greedy algorithms, in Fundamentals of computational theory, Lect. Notes Comput. Sci. 117, 205-209 (1981;

Zbl 0473.68019)] (greedoids). It is shown that the greedy algorithm optimizes all linear objective functions if and only if the problem structure (phrased in terms of either accessible set systems or hereditary languages) is a matroid embedding. An exact characterization of the objective functions optimized by the greedy algorithm on matroid embeddings is also presented. Finally, the authors present an exact characterization of the structures on which the greedy algorithm optimizes all bottleneck functions, structures that are less constrained than matroid embeddings.