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