A polynomial-time algorithm for knapsack with divisible item sizes

DOI10.1016/S0020-0190(97)00061-6zbMath1337.68140OpenAlexW2030493804MaRDI QIDQ287072

Wim F. J. Verhaegh, Emile H. L. 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)

Related Items (6)

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

Cites Work

• Unnamed Item
• Unnamed Item
• Integer knapsack and flow covers with divisible coefficients: Polyhedra, optimization and separation
• The cutting stock problem and integer rounding

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