Improved Exponential Time Lower Bound of Knapsack Problem Under BT Model

DOI10.1007/978-3-540-72504-6_57MaRDI QIDQ5425476zbMATH OpenOpenAlexFDO

Authors Tian Liu, Han Peng, Liyan Qian, Hongtao Sun, Jin Xu, Ke Xu, Jiaqi Zhu, Xin Li

Publication date 13 November 2007

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-72504-6_57

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) General topics in the theory of algorithms (68W01) Approximation algorithms (68W25) Combinatorial optimization (90C27) Abstract computational complexity for mathematical programming problems (90C60)

Recommendations

• On exponential time lower bound of Knapsack under backtracking
• Improved lower and upper bounds for the number of feasible solutions to a knapsaek problem
• Improved approximation algorithms for a bilevel knapsack problem
• Improved approximation algorithms for a bilevel knapsack problem
• Publication:3481489
• An empirical analysis of exact algorithms for the unbounded knapsack problem
• The efficiency enhanced branch and bound algorithm for the knapsack model
• Improved approximation results for stochastic knapsack problems
• A faster exact method for large-scale knapsack problems with setup costs and times
• Upper and lower bounds for the complexity of the branch and bound method for the knapsack problem

Cited in

(2)

• Toward a model for backtracking and dynamic programming
• On exponential time lower bound of Knapsack under backtracking

This page was built for publication: Improved Exponential Time Lower Bound of Knapsack Problem Under BT Model

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5425476)