An O (n)-algorithm for LP-knapsacks with a fixed number of GUB constraints
| Autor(en): | Brucker, P. | Stichwörter: | MATHEMATICAL PROGRAMMING, LINEAR | Erscheinungsdatum: | 1984 | Herausgeber: | Physica-Verlag | Enthalten in: | Zeitschrift für Operations Research | Band: | 28 | Ausgabe: | 1 | Startseite: | 29 | Seitenende: | 40 | Zusammenfassung: | An O (n+r log n) algorithm is presented for the linear programming knapsack problem with r generalized upper bounds and n variables. This result which is based on parametric programming and well-known ideas for the design of linear-time algorithms improves O (n log n) algorithms given by Glover/Klingman [1979] and Zemel [1980]. © 1984 Physica-Verlag. |
ISSN: | 03409422 | DOI: | 10.1007/BF01919085 | Externe URL: | https://www.scopus.com/inward/record.uri?eid=2-s2.0-0021371811&doi=10.1007%2fBF01919085&partnerID=40&md5=91f4d9909c603c326673bf892bb10702 |
Zur Langanzeige
