QQ客服 官方微博 反馈留言

	Improved exponential time lower bound of knapsack problem under BT model
	Xin, Li ; Tian, Liu ; Han, Peng ; Liyan, Qian ; Hongtao, Sun ; Jin, Xu ; Ke, Xu ; Jiaqi, Zhu
	2007
英文摘要	M. Alekhnovich et al. have recently proposed a model of algorithms, called BT model, which covers Greedy, Backtracking and Simple Dynamic Programming algorithms and can be further divided into three kinds of fixed, adaptive and fully adaptive ones, and have proved exponential time lower bounds of exact and approximation algorithms under adaptive BT model for Knapsack problem which are about ??(20.5n/??/n) and ??((1/??) 0,315)(for approximation ratio 1 - ??), respectively (M. Alekhovich, A. Borodin, J. Buresh-Oppenheim, R. Impagliazzo, A. Magen, and T. Pitassi, Toward a Model for Backtracking and Dynamic Programming, Proceedings of Twentieth Annual IEEE Conference on Computational Complexity, pp308-322, 2005). In this short note, we slightly improve their lower bounds to ??(2 0.66n/??n) and ??((1/??)0.420), respectively, through more complicated combinatorial arguments, and propose as an open question what is the best achievable lower bound for Knapsack problem under the adaptive BT model. ? Springer-Verlag Berlin Heidelberg 2007.; EI; 0
语种	英语
内容类型	其他
源URL	[http://ir.pku.edu.cn/handle/20.500.11897/409897]
专题	信息科学技术学院
推荐引用方式 GB/T 7714	Xin, Li,Tian, Liu,Han, Peng,et al. Improved exponential time lower bound of knapsack problem under BT model. 2007-01-01.

个性服务

查看访问统计

相关权益政策

暂无数据

收藏/分享

除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。