Computer Science – Computational Complexity
Scientific paper
2006-06-14
Computer Science
Computational Complexity
9 pages, 3 figures
Scientific paper
M.Alekhnovich et al. recently have proposed a model of algorithms, called BT model, which covers Greedy, Backtrack and Simple Dynamic Programming methods and can be further divided into fixed, adaptive and fully adaptive three kinds, and have proved exponential time lower bounds of exact and approximation algorithms under adaptive BT model for Knapsack problem which are $\Omega(2^{n/2}/\sqrt n)=\Omega(2^{0.5n}/\sqrt n)$ and $\Omega((1/\epsilon)^{1/3.17})\approx\Omega((1/\epsilon)^{0.315})$(for approximation ratio $1-\epsilon$) respectively (M. Alekhovich, A. Borodin, J. Buresh-Oppenheim, R. Impagliazzo, A. Magen, and T. Pitassi, Toward a Model for Backtracking and Dynamic Programming, \emph{Proceedings of Twentieth Annual IEEE Conference on Computational Complexity}, pp308-322, 2005). In this note, we slightly improved their lower bounds to $\Omega(2^{(2-\epsilon)n/3}/\sqrt{n})\approx \Omega(2^{0.66n}/\sqrt{n})$ and $\Omega((1/\epsilon)^{1/2.38})\approx\Omega((1/\epsilon)^{0.420})$, and proposed as an open question what is the best achievable lower bounds for knapsack under adaptive BT models.
Li Xin
Liu Tian
Peng Han
Sun Hongtao
Zhu Jiaqi
No associations
LandOfFree
Improved Exponential Time Lower Bound of Knapsack Problem under BT model does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Improved Exponential Time Lower Bound of Knapsack Problem under BT model, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Improved Exponential Time Lower Bound of Knapsack Problem under BT model will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-196925