ISSN:
1436-5057
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
Description / Table of Contents:
Zusammenfassung Wir betrachten Lineare Programme der Form {maxcx|1≤Ax≤b,L≤x≤U} mit nichtnegativen Vektorenl,b,L,U und einer 0–1 MatrixA, die von “Manhattan Skyline” Form ist, d. h. der Träger jeder Zeile vonA ist im Träger jeder folgenden Zeile enthalten. Wir stellen einenO(nm+nlogn)-Algorithmus zur Lösung solcher Probleme vor und untersuchen seinen Anwendungsbereich.
Notes:
Abstract We consider LP's of the form max {cx|l≤Ax≤b, L≤x≤U} where,l,b,L,U are nonnegative andA is a 0–1 matrix which looks like “Manhattan Skyline”, i.e. the support of each row is contained in the support of every subsequent row. AnO(nm+nlogn) algorithm is presented for solving the problem.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF02252513
Permalink
