• 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

Metadaten
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