Yet harder knapsack problems

DOI10.1016/j.tcs.2011.07.003zbMath1233.68145MaRDI QIDQ653327

Georg Schnitger, Stasys P. Jukna

Publication date: 9 January 2012

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

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

zbMATH Keywords

dynamic programming; branch and bound; knapsack; perfect matching; memoization; branching program

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

90C39: Dynamic programming

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

Related Items

Features for the 0-1 knapsack problem based on inclusionwise maximal solutions, A new class of hard problem instances for the 0-1 knapsack problem

Cites Work

• A stronger model of dynamic programming algorithms
• Bounds on the size of branch-and-bound proofs for integer knapsacks
• On the size of (generalized) OBDDs for threshold functions
• Neither reading few bits twice nor reading illegally helps much
• Size of ordered binary decision diagrams representing threshold functions
• On P versus NP\(\cap\)co-NP for decision trees and read-once branching programs
• On lower bounds for read-\(k\)-times branching programs
• Simple lifted cover inequalities and hard knapsack problems
• A hard knapsack problem
• Hard Knapsack Problems
• A note on read-$k$ times branching programs
• Lifted Cover Inequalities for 0-1 Integer Programs: Complexity
• Branching Programs and Binary Decision Diagrams
• Trivial integer programs unsolvable by branch-and-bound
• On cliques in graphs