A polynomial-time algorithm for knapsack with divisible item sizes

DOI10.1016/S0020-0190(97)00061-6MaRDI QIDQ287072zbMATH OpenOpenAlexFDO

Authors W. F. J. Verhaegh, E. Aarts

Publication date 26 May 2016

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0020-0190(97)00061-6

zbMATH Keywords

computational complexitycombinatorial problemsknapsack

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorial optimization (90C27)

Recommendations

• A polynomial algorithm for the multiple knapsack problem with divisible item sizes
• A polynomially solvable special case of the unbounded knapsack problem
• scientific article; zbMATH DE number 3876925
• Unbounded knapsack problems with arithmetic weight sequences
• A well-solvable special case of the bounded knapsack problem

Cites work

• scientific article; zbMATH DE number 44282 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• Integer knapsack and flow covers with divisible coefficients: Polyhedra, optimization and separation
• The cutting stock problem and integer rounding

Cited in

(8)

• A polynomially solvable special case of the unbounded knapsack problem
• The complexity of multidimensional periodic scheduling
• A polynomial algorithm for the multiple knapsack problem with divisible item sizes
• Unbounded knapsack problems with arithmetic weight sequences
• A new upper bound for the multiple knapsack problem
• Combinatorial algorithms for solving the constrained knapsack problems with divisible item sizes and penalties
• A well-solvable special case of the bounded knapsack problem
• When greedy gives optimal: a unified approach

This page was built for publication: A polynomial-time algorithm for knapsack with divisible item sizes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q287072)