| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 437871 | Theoretical Computer Science | 2010 | 6 Pages |
We prove an time lower bound of Knapsack problem under the adaptive priority branching trees (pBT) model. The pBT model is a formal model of algorithms covering backtracking and dynamic programming [M. Alekhnovich, A. Borodin, A. Magen, J. Buresh-Oppenheim, R. Impagliazzo, T. Pitassi, Toward a model for backtracking and dynamic programming, ECCC TR09-038, 2009. Earlier version in Proc 20th IEEE Computational Complexity, 2005, pp. 308–322]. Our result improves the lower bound of M. Alekhovich et al. and the lower bound of Li et al. [X. Li, T. Liu, H. Peng, L. Qian, H. Sun, J. Xu, K. Xu, J. Zhu, Improved exponential time lower bound of Knapsack problem under BT model, in: Proc 4th TAMC 2007, in: LNCS, vol. 4484, 2007, pp. 624–631] through optimized arguments.
