×
Fayard, D.; Plateau, G.

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

Computing 28, 269-287 (1982).
Page: −5 −4 −3 −2 −1 ±0 +1 +2 +3 +4 +5 Show Scanned Page
scan of Zbl 0468.90045

Cited in 1 Review
Cited in 48 Documents

MSC:

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

Keywords:

0-1 knapsack problem; implicit enumeration algorithm; FPK 79; implementation; computational results; binary knapsack

Software:

Quicksort; Algorithm 37
PDF BibTeX XML Cite
\textit{D. Fayard} and \textit{G. Plateau}, Computing 28, 269--287 (1982; Zbl 0468.90045)
Full Text: DOI
  • logo of hbz
  • logo of WorldCat

References:

[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.