Yet harder knapsack problems

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

zbMATH Keywords

dynamic programmingbranch and boundknapsackperfect matchingmemoizationbranching 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)

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