ISSN:
1436-5057
Schlagwort(e):
90C05
;
90C35
;
Linear programming
;
network flows
;
tree
Quelle:
Springer Online Journal Archives 1860-2000
Thema:
Informatik
Beschreibung / Inhaltsverzeichnis:
Zusammenfassung Kern [1986] entwicklete einenO(nm+n logn)-Algorithmus zur Lösung von linearen Programmen der Form max{cx/l≤Ax≤b, L≤x≤U}, wobeil, b, L, U nichtnegativ sind undA eine 0-1-Matrix der Dimensionm x n mit der Eigenschaft, daß der Träger jeder Zeile vonA im Träger jeder der nachfolgenden Zeilen enthalten ist, darstellt. Wir zeigen, daß eine allgemeinere Klasse von linearen Programmen sich mit einem Aufwand vonO (n logn), lösen läßt.
Notizen:
Abstract AnO(nm+nlogn)-algorithm was developed by Kern, [1986] to solve linear programs of the form max{cx/l≤Ax≤b, L≤x≤U} wherel, b, L, U are nonnegative andA is a 0-1-matrix of dimensionm x n with the property that the support of each row is contained in the support of every subsequent row. We will show that a more general class of linear programs can be solved inO(n logn)-time.
Materialart:
Digitale Medien
URL:
http://dx.doi.org/10.1007/BF02243226
Permalink
