On Exponential Time Lower Bound of Knapsack under Backtracking

Details On Exponential Time Lower Bound of Knapsack under Backtracking On Exponential Time Lower Bound of Knapsack under Backtracking

2007-12-20

arxiv.org/abs/0712.3348v2

Computer Science

Computational Complexity

This paper supersedes the result of arXiv:cs/0606064

Scientific paper

M.Aleknovich et al. have recently proposed a model of algorithms, called BT model, which generalizes both the priority model of Borodin, Nielson and Rackoff, as well as a simple dynamic programming model by Woeginger. BT model can be further divided into three kinds of fixed, adaptive and fully adaptive ones. They have proved exponential time lower bounds of exact and approximation algorithms under adaptive BT model for Knapsack problem. Their exact lower bound is $\Omega(2^{0.5n}/\sqrt{n})$, in this paper, we slightly improve the exact lower bound to about $\Omega(2^{0.69n}/\sqrt{n})$, by the same technique, with related parameters optimized.

Affiliated with

Also associated with

No associations

Rating

On Exponential Time Lower Bound of Knapsack under Backtracking 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 On Exponential Time Lower Bound of Knapsack under Backtracking, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On Exponential Time Lower Bound of Knapsack under Backtracking will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-2724