On exponential time lower bound of Knapsack under backtracking

DOI10.1016/J.TCS.2009.12.004MaRDI QIDQ964408zbMATH OpenOpenAlexFDO

Authors Tian Liu, Xin Li

Publication date 15 April 2010

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2009.12.004

zbMATH Keywords

backtrackingexponential time lower boundsknapsack problemmodel of algorithmspBT model

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

• Improved Exponential Time Lower Bound of Knapsack Problem Under BT Model
• Toward a model for backtracking and dynamic programming
• Yet harder knapsack problems
• scientific article; zbMATH DE number 1559524
• An alternative to Ben-Or's lower bound for the knapsack problem complexity

Cites work

• (Incremental) priority algorithms
• A Sufficient Condition for Backtrack-Free Search
• Approximation and Online Algorithms
• Computing Partitions with Applications to the Knapsack Problem
• Exponential lower bounds for the running time of DPLL algorithms on satisfiable formulas
• Further Reflections on a Theory for Basic Algorithms
• Hard Knapsack Problems
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1953201 (Why is no real title available?)
• Improved Exponential Time Lower Bound of Knapsack Problem Under BT Model
• Many hard examples in exact phase transitions
• Models of greedy algorithms for graph problems
• Priority algorithms for the subset-sum problem
• Proofs as Games
• The power of priority algorithms for facility location and set cover
• Toward a model for backtracking and dynamic programming

Cited in

(4)

• New worst-case upper bound for counting exact satisfiability
• Lower Bounds on Time-Accuracy Trade-Offs for the 0-1 Knapsack Problem
• Toward a model for backtracking and dynamic programming
• Improved Exponential Time Lower Bound of Knapsack Problem Under BT Model

This page was built for publication: On exponential time lower bound of Knapsack under backtracking

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