In den Foilen steht ein Satz:
Ein Greedy-Algorithmus liefert immer eine optimale Lösung, wenn das Problem eine matroide Struktur hat.
Was für eine matroide Struktur ist hier gemeint?

gibts da mehrere von?

was eine matroide Struktur ist muss man wohl nicht wissen,
vielleicht hilft dir diese Seite weiter:
http://matheplanet.com/default3.html?call=article.php?sid=14


(möglichst im Titel die Vorlesung nennen, zu der die Frage gehört)

Schön ist auch die Behandlung in dem ersten Band der "Vorlesungen über Informatik" Reihe von Goos (ab S.333). Dort wird auch der Zusammenhang zu gierigen Algorithmen gezeigt. Das Kapitel ist nur 3 Seiten oder so lang, falls also jemand Interesse hat, es ist nicht soo viel Arbeit [img]http://www.fb18.de/gfx/25.gif[/img]

Cheers,
Frank

Vielen Dank fuer den Hinweis. Das hat mir geholfen.