A polynomial-time algorithm for knapsack with divisible item sizes

DOI10.1016/S0020-0190(97)00061-6zbMATH Open1337.68140OpenAlexW2030493804MaRDI QIDQ287072FDOQ287072

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

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

zbMATH Keywords

computational complexitycombinatorial problemsknapsack

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Integer knapsack and flow covers with divisible coefficients: Polyhedra, optimization and separation
• The cutting stock problem and integer rounding

Cited In (8)

• Unbounded knapsack problems with arithmetic weight sequences
• Combinatorial algorithms for solving the constrained knapsack problems with divisible item sizes and penalties
• 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
• A new upper bound for the multiple knapsack problem
• 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)