Yet harder knapsack problems
From MaRDI portal
Publication:653327
DOI10.1016/j.tcs.2011.07.003zbMath1233.68145OpenAlexW2082847241MaRDI 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
Analysis of algorithms and problem complexity (68Q25) Dynamic programming (90C39) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items (2)
A new class of hard problem instances for the 0-1 knapsack problem ⋮ Features for the 0-1 knapsack problem based on inclusionwise maximal solutions
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
This page was built for publication: Yet harder knapsack problems
