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.
Preview
Unable to display preview. Download preview PDF.
References
J. Edmonds, “Matroids and the greedy algorithm”, mimeographed notes, International Symposium on Mathematical Programming (Princeton, NJ, 1966), pp. 93–117.
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).
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.
T.A. Jenkyns, “p-systems as intersections of matroids”, in: Proceedings of the eighth Southeastern conference on combinatorics, graph theory, and computing, to appear.
T.A. Jenkyns, “The greedy travelling salesman's problem”, Networks, to appear.
B. Korte and D. Hausmann, “An analysis of the greedy heuristic for independence systems”, Annals of Discrete Mathematics 2 (1978) 65–74.
Author information
Authors and Affiliations
Editor information
Rights 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