Yet harder knapsack problems
From MaRDI portal
Publication:653327
DOI10.1016/J.TCS.2011.07.003zbMATH Open1233.68145OpenAlexW2082847241MaRDI QIDQ653327FDOQ653327
Authors: Georg Schnitger, Stasys 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
Recommendations
Analysis of algorithms and problem complexity (68Q25) Dynamic programming (90C39) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Cites Work
- Branching Programs and Binary Decision Diagrams
- On cliques in graphs
- On lower bounds for read-\(k\)-times branching programs
- A note on read-$k$ times branching programs
- Lifted Cover Inequalities for 0-1 Integer Programs: Complexity
- Hard Knapsack Problems
- A stronger model of dynamic programming algorithms
- Trivial integer programs unsolvable by branch-and-bound
- 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
- Simple lifted cover inequalities and hard knapsack problems
- A hard knapsack problem
- Bounds on the size of branch-and-bound proofs for integer knapsacks
Cited In (8)
- On exponential time lower bound of Knapsack under backtracking
- Title not available (Why is that?)
- 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
- Where are the hard knapsack problems?
- A hard knapsack problem
- Bounds on the size of branch-and-bound proofs for integer knapsacks
- Limitations of incremental dynamic programming
This page was built for publication: Yet harder knapsack problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q653327)
