Skip to main content
SpringerLink
Log in

Worst case analysis of greedy type algorithms for independence systems

  • Chapter
  • First Online:
Combinatorial Optimization

Part of the book series: Mathematical Programming Studies ((MATHPROGRAMM,volume 12))

Abstract

This paper deals with results on performance measures of greedy type algorithms for maximization or minimization problems on general independence systems which were given by the authors independently in earlier papers ([3] and [6]). Besides a unified formulation of the earlier results some modifications and extensions are presented here underlining the central role which the greedy algorithm plays in combinatorial optimization.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

References

  1. J. Edmonds, “Matroids and the greedy algorithm”, mimeographed notes, International Symposium on Mathematical Programming (Princeton, NJ, 1966), pp. 93–117.

    Google Scholar 

  2. D. Hausmann and B. Korte, “K-Greedy algorithm for independence systems”, working paper No. 7764-OR, Institut für ökonometrie und Operations Research, University of Bonn (Bonn, June 1977).

    Google Scholar 

  3. T.A. Jenkyns, “The efficacy of the “greedy” algorithm”, in: Proceedings of the seventh Southeastern conference on combinatorics, graph theory, and computing pp. 341–350.

    Google Scholar 

  4. T.A. Jenkyns, “p-systems as intersections of matroids”, in: Proceedings of the eighth Southeastern conference on combinatorics, graph theory, and computing, to appear.

    Google Scholar 

  5. T.A. Jenkyns, “The greedy travelling salesman's problem”, Networks, to appear.

    Google Scholar 

  6. B. Korte and D. Hausmann, “An analysis of the greedy heuristic for independence systems”, Annals of Discrete Mathematics 2 (1978) 65–74.

    Article  MATH  MathSciNet  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Universität Bonn, Bonn, Federal Republic of Germany

    D. Hausmann & B. Korte

  2. Brock University, St. Catherines, Ont., Canada

    T. A. Jenkyns

Authors
  1. D. Hausmann
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. B. Korte
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. T. A. Jenkyns
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

M. W. Padberg

Rights and permissions

Reprints and permissions

Copyright information

© 1980 The Mathematical Programming Society

About this chapter

Cite this chapter

Hausmann, D., Korte, B., Jenkyns, T.A. (1980). Worst case analysis of greedy type algorithms for independence systems. In: Padberg, M.W. (eds) Combinatorial Optimization. Mathematical Programming Studies, vol 12. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0120891

Download citation

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

  • Received:

  • Revised:

  • Published:

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-642-00801-6

  • Online ISBN: 978-3-642-00802-3

  • eBook Packages: Springer Book Archive

Publish with us

Policies and ethics

Search

Navigation