Yet harder knapsack problems

DOI10.1016/J.TCS.2011.07.003MaRDI QIDQ653327zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

dynamic programmingbranch and boundperfect matchingknapsackmemoizationbranching program

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Dynamic programming (90C39) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• A hard knapsack problem
• Where are the hard knapsack problems?
• scientific article; zbMATH DE number 1783857
• scientific article; zbMATH DE number 1302173
• An algorithm for solving a class of knapsack problems and its generalization

Cites work

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

Cited in

(8)

• A hard knapsack problem
• scientific article; zbMATH DE number 1783857 (Why is no real title available?)
• Limitations of incremental dynamic programming
• 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
• Bounds on the size of branch-and-bound proofs for integer knapsacks
• Where are the hard knapsack problems?
• On exponential time lower bound of Knapsack under backtracking

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)