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
Additional Services
| 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 |
