Bachmann, Peter Ein Beitrag zur Maximierung submodularer und isotoner Funktionen über Unabhängigkeitssystemen. (German) Zbl 0556.90058 Wiss. Z. Tech. Hochsch. Karl-Marx-Stadt 26, 167-172 (1984). Gegenstand des Artikels ist die Maximierung einer submodularen und isotonen Funktion über einem Unabhängigkeitssystem durch Anwendung eines Greedyalgorithmus. Ausgehend von einer aus der Literatur bekannten Aussage, die eine Güteabschätzung der dabei gewonnenen Lösung gestattet, werden asymptotisch erreichbare schärfste Schranken für diese Abschätzung angegeben. Ferner wird eine Fehlerschranke bewiesen, die nur vom Rangquotient des Unabhängigkeitssystems abhängt. MSC: 90C10 Integer programming 90C30 Nonlinear programming 65K05 Numerical mathematical programming methods Keywords:submodular function; independence system; greedy-type-algorithm; worst- case-analysis; rank quotient; isotone function; asymptotic error bound PDFBibTeX XMLCite \textit{P. Bachmann}, Wiss. Z. Tech. Hochsch. Karl-Marx-Stadt 26, 167--172 (1984; Zbl 0556.90058)