×

zbMATH — the first resource for mathematics

An O(n) algorithm for the multiple-choice knapsack linear program. (English) Zbl 0532.90068
Summary: An algorithm for solving the linear program associated with the multiple choice knapsack problem is described. The algorithm is shown to work in time linear in the number of variables. This improves the previously known best bound for this problem, and is optimal to within a constant factor.

MSC:
90C08 Special problems of linear programming (transportation, multi-index, data envelopment analysis, etc.)
90C05 Linear programming
65K05 Numerical mathematical programming methods
68Q25 Analysis of algorithms and problem complexity
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] A.V. Aho, J.E. Hopcroft and J.D. Ullman,The design and analysis of Computer algorithms (Addison-Wesley, Reading, MA, 1974). · Zbl 0326.68005
[2] E. Balas and E. Zemel, An algorithm for large zero-one knapsack problems.Operations Research 28 (1980) 1132–1154 · Zbl 0449.90064
[3] M.E. Dyer, A geometrical approach to two-constraint linear programs with generalised upper bounds, Research Report, Teesside Polytechnic (1981).
[4] M.E. Dyer, Two-variable linear programs are solvable in linear time, Research Report, Teesside Polytechnic (1981).
[5] F. Glover and D. Klingman, A O(n logn) algorihtm for LP knapsacks with GUB constraints,Mathematical Programming 17 (1979) 345–361. · Zbl 0421.90050
[6] T. Ibaraki, T. Hasegawa, K. Teranaka and J. Iwase, The multiple choice knapsack problem,Journal of the Operations Research Society of Japan 21 (1978) 59–95. · Zbl 0379.90076
[7] R.T. Rockafellar,Convex analysis (Princeton University Press, Princeton, NJ, 1970). · Zbl 0193.18401
[8] P. Sinha and A. Zoltners, The multiple choice knapsack problem,Operations Research 27 (1979) 503–515. · Zbl 0406.90052
[9] E. Zemel, The linear multiple choice knapsack problem,Operations Reseach 28 (1980) 1412–1423. · Zbl 0447.90064
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.