UNIVERSITÄTSBIBLIOTHEK

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.

Volltext Dateien herunterladen

Metadaten exportieren

Metadaten
Verfasserangaben:Lara Turner, Matthias Ehrgott, Horst W. Hamacher
URN (Permalink):urn:nbn:de:hbz:386-kluedo-35355
Schriftenreihe (Bandnummer):Report in Wirtschaftsmathematik (WIMA Report) (147)
Dokumentart:Preprint
Sprache der Veröffentlichung:Englisch
Veröffentlichungsdatum (online):18.06.2013
Jahr der Verö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:Fachbereich Mathematik
DDC-Sachgruppen:5 Naturwissenschaften und Mathematik / 510 Mathematik
Lizenz (Deutsch):Standard gemäß KLUEDO-Leitlinien vom 10.09.2012