Hard Knapsack Problems
From MaRDI portal
Publication:3893671
DOI10.1287/opre.28.6.1402zbMath0447.90063OpenAlexW1970290925MaRDI QIDQ3893671
Publication date: 1980
Published in: Operations Research (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1287/opre.28.6.1402
computational complexitybranch-and-boundrecursive algorithmhard knapsack problemsrudimentary divisibility argumentszero-one knapsack problem
Analysis of algorithms and problem complexity (68Q25) Dynamic programming (90C39) Boolean programming (90C09)
Related Items
An efficient preprocessing procedure for the multidimensional 0-1 knapsack problem, Exact methods for the knapsack problem and its generalizations, Column basis reduction and decomposable knapsack problems, Vašek Chvátal: a very short introduction (on the occasion of his 60th birthday), A new class of hard problem instances for the 0-1 knapsack problem, A new enumeration scheme for the knapsack problem, A hybrid dynamic programming/branch-and-bound algorithm for the multiple- choice knapsack problem, Multivariable Branching: A 0-1 Knapsack Problem Case Study, The knapsack problem with generalized upper bounds, A new fully polynomial time approximation scheme for the interval subset sum problem, Some thoughts on combinatorial optimisation, Branch-and-bound solves random binary IPs in poly\((n)\)-time, Compressing branch-and-bound trees, An efficient fully polynomial approximation scheme for the Subset-Sum problem., A theoretical and computational analysis of full strong-branching, Complexity of optimizing over the integers, Lower bounds on the size of general branch-and-bound trees, Complexity of branch-and-bound and cutting planes in mixed-integer optimization, Features for the 0-1 knapsack problem based on inclusionwise maximal solutions, Advice complexity of adaptive priority algorithms, Heuristics and their design: A survey, Toward a model for backtracking and dynamic programming, Bounds on the size of branch-and-bound proofs for integer knapsacks, Yet harder knapsack problems, Thinner is not always better: cascade knapsack problems, Simultaneously lifting sets of binary variables into cover inequalities for knapsack polytopes, On exponential time lower bound of Knapsack under backtracking, A solution method for a knapsack problem and its variant, Measuring instance difficulty for combinatorial optimization problems, A stronger model of dynamic programming algorithms, Revisiting \textit{where are the hard knapsack problems?} Via instance space analysis, An exact algorithm for the subset sum problem, Using modifications to Grover's search algorithm for quantum global optimization, Solving dense subset-sum problems by using analytical number theory, Complexity of branch-and-bound and cutting planes in mixed-integer optimization. II, Lower bound on size of branch-and-bound trees for solving lot-sizing problem, A note on the complexity of a partition algorithm, Simple lifted cover inequalities and hard knapsack problems, A transformation of hard (equality constrained) knapsack problems into constrained shortest path problems, Approximation schemes for the subset-sum problem: Survey and experimental analysis, Pseudopolynomial algorithms for the solution of backpack problems
