An Exact Characterization of Greedy Structures
Paul Helman, Bernard M. E. Moret, Henry D. Shapiro
Source abstract
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 Rado [A note on independent functions, Proc. London Math. Soc., 7 (1957), pp. 300–320], Gale [Optimal assignments in an ordered set, J. Combin. Theory, 4 (1968), pp. 176–180], and Edmonds [Matroids and the greedy algorithm, Math. Programming, 1 (1971), pp. 127–136], (matroids), and of Korte and Lovasz [Greedoids and linear object functions, SIAM J. Alg. Discrete Meth., 5 (1984), pp. 239–248] and [Mathematical structures underlying greedy algorithms, in Fundamentals of Computational Theory, LNCS 177, Springer-Verlag, 1981, pp. 205–209] (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.
Evidence graph
No public relationships recorded yet.
Integrity note: This page is a factual metadata record created by deterministic ingestion. It is not a claim that the work moves a mathematical frontier or has been independently verified.