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.
Verfasser*innenangaben: | Lara Turner, Matthias Ehrgott, Horst W. Hamacher |
---|---|
URN: | urn:nbn:de:hbz:386-kluedo-35355 |
Schriftenreihe (Bandnummer): | Report in Wirtschaftsmathematik (WIMA Report) (147) |
Dokumentart: | Preprint |
Sprache der Veröffentlichung: | Englisch |
Datum der Veröffentlichung (online): | 18.06.2013 |
Jahr der Erstveröffentlichung: | 2013 |
Veröffentlichende Institution: | Technische Universität Kaiserslautern |
Datum der Publikation (Server): | 19.06.2013 |
Freies Schlagwort / Tag: | Combinatorial optimization; Greedy algorithm; Matroids; Uniform matroids; Universal objective function |
Seitenzahl: | 28 |
Fachbereiche / Organisatorische Einheiten: | Kaiserslautern - Fachbereich Mathematik |
DDC-Sachgruppen: | 5 Naturwissenschaften und Mathematik / 510 Mathematik |
Lizenz (Deutsch): | Standard gemäß KLUEDO-Leitlinien vom 10.09.2012 |