A lower time bound for the knapsack problem on random access machines. (English) Zbl 0515.68037
MSC:
| 68Q25 | Analysis of algorithms and problem complexity |
| 90C10 | Integer programming |
| 68Q05 | Models of computation (Turing machines, etc.) (MSC2010) |
Keywords:
random access machines; computational model; decision tree arguments; linear decision treesReferences:
| [1] | Paul, W.J., Simon, J.: Decision Trees and Random Access Machines. Symposium ?ber Logik und Algorithmik, Z?rich 1980 |
| [2] | Dobkin, D., Lipton, R.: A Lower Bound of 1/2n 2 on Linear Search Programs for the Knapsack Problem. J.C.S.S. 16, 417-421 (1975) · Zbl 0397.68045 |
| [3] | Aho, A., Hopcroft, J.E., Ullman, J.D.: The Design and Analysis of Computer Algorithmus. Reading, MA: Addison-Wesley 1974 · Zbl 0326.68005 |
| [4] | Yajima, S., Ibanaki, T.: A Lower Bound on the Number of Threshold Functions. IEEE-EC 14, 926-929 (1965) · Zbl 0135.18205 |
| [5] | Blaschke, W.: ?ber den gr??ten Kreis in einer konvexen Punktmenge. Jahresbericht der deutschen Mathematiker Vereinigung 23, 369-374 (1914) · JFM 45.0622.01 |
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
