ISSN:
1436-5057
Keywords:
90C05
;
90C35
;
Linear programming
;
network flows
;
tree
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
Description / Table of Contents:
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.
Notes:
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.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF02243226
Permalink