A Polynomial Linear Search Algorithm for the n -Dimensional Knapsack Problem
- 26 June 1984
- journal article
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 31 (3) , 668-676
- https://doi.org/10.1145/828.322450
Abstract
We present a Linear Search Algorithm which decides the n-dimensional knapsack problem in n4log(n) + 0.(n3) steps. This algorithm works for inputs consisting of n numbers for some arbitrary but fixed integer n. This result solves an open problem posed for example in [6] and [7] by Dobkin / Lipton and A.C.C. Yao, resp.. It destroys the hope of proving large lower bounds for this NP-complete problem in the model of Linear Search Algorithms.Keywords
This publication has 3 references indexed in Scilit:
- A lower time bound for the knapsack problem on random access machinesActa Informatica, 1983
- Khachiyan's linear programming algorithmJournal of Algorithms, 1980
- A lower bound of 12n2 on linear search programs for the Knapsack problemJournal of Computer and System Sciences, 1978