Skip to main content
Log in

Matroids and the greedy algorithm

  • Published:
Mathematical Programming Submit manuscript

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.

Access this article

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Jack Edmonds, “Maximum matching and a polyhedron with {0, 1}-vertices,”Journal of Research of the National Bureau of Standards 69B (1965) 125–130.

    Google Scholar 

  2. Jack Edmonds, “Matroid partition, Math. of the Decision Sciences,”American Mathematical Society Lectures in Applied Mathematics 11 (1968) pp. 335–345.

    Google Scholar 

  3. Jack Edmonds, “Optimum branchings,”Journal of Research of the National Bureau of Standards 71B (1967) 233–240; reprinted with [2], pp. 346–361.

    Google Scholar 

  4. Jack Edmonds, “Systems of distinct representatives and linear algebra,”Journal of Research National Bureau of Standards 71B (1967) 241–245.

    Google Scholar 

  5. J.B. Kruskal, On the shortest spanning subtree of a graph and the traveling salesman problem,Proceedings American Mathematical Society 7 (1956) 48–50.

    Google Scholar 

  6. P. Rosenstiehl, “L'arbre minimum d'un graphe,”Proc. Int'l. Symp. on the Theory of Graphs in Rome 1966 (Dunod/Gordon-Breach, 1967).

  7. R. Rado, “Note on independence functions,”Proceedings London Mathematical Society 7 (1957) 300–320.

    Google Scholar 

  8. H. Whitney, “On the abstract properties of linear dependence,”American Journal of Mathematics 57 (1935) 509–533.

    Google Scholar 

Download references

Author information

Authors and Affiliations

Authors

Rights and permissions

Reprints 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

Download citation

  • Issue Date:

  • DOI: https://doi.org/10.1007/BF01584082

Keywords

Navigation