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.
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.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Faaland, B.: A weighted selection algorithm for certain tree structured linear programs. Operations Research32, 405–422 (1984).
Glover: Flows in arborescences. Management, Science17, 568–586 (1971).
Erenguc, S.: An algorithm for solving a class of linear programming problems, Discussion Paper No. 118, Center for Econometrics and Decision Sciences, University of Florida, Gainesville (1985).
Hoffman, A. J., Kolen, A. W., Sakarowitch, M.: Totally-balanced and greedy matrices. SIAM J. Alg. Disc. Meth.6, 721–730 (1985).
Author information
Authors and Affiliations
Additional information
Supported by the German Research Association (Deutsche Forschungsgemeinschaft, SFB 303).
Rights and permissions
About this article
Cite this article
Kern, W. An efficient algorithm for solving a special class of LP's. Computing 37, 219–226 (1986). https://doi.org/10.1007/BF02252513
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF02252513