• search hit 8 of 32
Back to Result List

On the Generality of the Greedy Algorithm for Solving Matroid Base Problems

  • It is well known that the greedy algorithm solves matroid base problems for all linear cost functions and is, in fact, correct if and only if the underlying combinatorial structure of the problem is a matroid. Moreover, the algorithm can be applied to problems with sum, bottleneck, algebraic sum or \(k\)-sum objective functions.

Download full text files

Export metadata

Author:Lara Turner, Matthias Ehrgott, Horst W. Hamacher
URN (permanent link):urn:nbn:de:hbz:386-kluedo-35355
Serie (Series number):Report in Wirtschaftsmathematik (WIMA Report) (147)
Document Type:Preprint
Language of publication:English
Publication Date:2013/06/18
Year of Publication:2013
Publishing Institute:Technische Universität Kaiserslautern
Date of the Publication (Server):2013/06/19
Tag:Combinatorial optimization; Greedy algorithm; Matroids; Uniform matroids; Universal objective function
Number of page:28
Faculties / Organisational entities:Fachbereich Mathematik
DDC-Cassification:5 Naturwissenschaften und Mathematik / 510 Mathematik
Licence (German):Standard gemäß KLUEDO-Leitlinien vom 10.09.2012