An algorithm for the solution of the 0-1 knapsack problem. (English) Zbl 0468.90045


90C09 Boolean programming
90C08 Special problems of linear programming (transportation, multi-index, data envelopment analysis, etc.)
65K05 Numerical mathematical programming methods
68Q25 Analysis of algorithms and problem complexity
90-04 Software, source code, etc. for problems pertaining to operations research and mathematical programming
Full Text: DOI


[1] Balas, E., Zemel, E.: An algorithm for large zero-one knapsack problems. Operations Research28, 1130–1154 (1980). · Zbl 0449.90064
[2] Fayard, D., Plateau, G.: Resolution of the 0–1 knapsack problem: comparison of methods. Mathematical Programming8, 272–307 (1975). · Zbl 0314.90062
[3] Fayard, D., Plateau, G.: Techniques de résolution du problème du knapsack en variables bivalentes: partie III. Publication 91, Laboratoire de Calcul, Université des Sciences et Techniques de Lille I, France (1977).
[4] Fayard, D., Plateau, G.: Reduction algorithms for single and multiple constraints 0–1 linear programming problems. Proceedings of the Congress Methods of Mathematical Programming, Zakopane, Poland, 1977.
[5] Fayard, D., Plateau, G.: On ”an efficient algorithm for the 0–1 knapsack problem, by Robert M. Nauss”. Management Science24, 918–919 (1978). · Zbl 0483.68063
[6] Fayard, D., Plateau, G.: Contribution à la résolution des programmes mathématiques en nombres entiers, Thèse d’Etat, Université des Sciences et Techniques de Lille I France, 1979.
[7] Greenberg, H., Hegerich, R. L.: A branch search algorithm for the knapsack problem. Management Science16, 327–332 (1970). · Zbl 0191.48401
[8] Lawler, E. L.: Fast approximation algorithms for knapsack problems. Mathematics of Operations Research4, 339–356 (1979). · Zbl 0425.90064
[9] Martello, S., Toth, P.: Algorithm for the solution of the 0–1 single knapsack. Computing21, 81–86 (1978). · Zbl 0389.90070
[10] Sedgewick, R.: Implementing Quicksort programs. Communications of ACM21, 847–857 (1978). · Zbl 0386.68058
[11] Walukiewicz, S.: The size reduction of a binary knapsack problem. Bulletin of the Polish Academy of Sciences, Series Sciences and Technics23 (1975). · Zbl 0322.90040
[12] Zoltners, A. A.: A direct descent binary knapsack problem. Journal of ACM25, 304–311 (1978). · Zbl 0372.68012
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.