Abstract
Linear-algebra rank is the solution to an especially tractable optimization problem. This tractability is viewed abstractly, and extended to certain more general optimization problems which are linear programs relative to certain derived polyhedra.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Jack Edmonds, “Maximum matching and a polyhedron with {0, 1}-vertices,”Journal of Research of the National Bureau of Standards 69B (1965) 125–130.
Jack Edmonds, “Matroid partition, Math. of the Decision Sciences,”American Mathematical Society Lectures in Applied Mathematics 11 (1968) pp. 335–345.
Jack Edmonds, “Optimum branchings,”Journal of Research of the National Bureau of Standards 71B (1967) 233–240; reprinted with [2], pp. 346–361.
Jack Edmonds, “Systems of distinct representatives and linear algebra,”Journal of Research National Bureau of Standards 71B (1967) 241–245.
J.B. Kruskal, On the shortest spanning subtree of a graph and the traveling salesman problem,Proceedings American Mathematical Society 7 (1956) 48–50.
P. Rosenstiehl, “L'arbre minimum d'un graphe,”Proc. Int'l. Symp. on the Theory of Graphs in Rome 1966 (Dunod/Gordon-Breach, 1967).
R. Rado, “Note on independence functions,”Proceedings London Mathematical Society 7 (1957) 300–320.
H. Whitney, “On the abstract properties of linear dependence,”American Journal of Mathematics 57 (1935) 509–533.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Edmonds, J. Matroids and the greedy algorithm. Mathematical Programming 1, 127–136 (1971). https://doi.org/10.1007/BF01584082
Issue Date:
DOI: https://doi.org/10.1007/BF01584082