On exponential time lower bound of Knapsack under backtracking

DOI10.1016/j.tcs.2009.12.004zbMath1194.68127OpenAlexW2057373223MaRDI QIDQ964408

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

knapsack problembacktrackingexponential time lower boundsmodel of algorithmspBT model

Mathematics Subject Classification ID

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

Related Items (1)

NEW WORST-CASE UPPER BOUND FOR COUNTING EXACT SATISFIABILITY

Cites Work

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

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