×

Ein Beitrag zur Maximierung submodularer und isotoner Funktionen über Unabhängigkeitssystemen. (German) Zbl 0556.90058

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
PDFBibTeX XMLCite