A polynomial algorithm for the multiple knapsack problem with divisible item sizes

DOI10.1016/j.ipl.2009.02.003zbMath1209.68704OpenAlexW2051575470MaRDI QIDQ987829

Paolo Detti

Publication date: 16 August 2010

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

Full work available at URL: https://doi.org/10.1016/j.ipl.2009.02.003

zbMATH Keywords

analysis of algorithmspolynomial algorithmsdivisible sizesmultiple knapsack problem

Mathematics Subject Classification ID

Analysis of algorithms (68W40)

Related Items (7)

Bin packing with divisible item sizes and rejection penalties ⋮ A Branch-and-Price Algorithm for the Multiple Knapsack Problem ⋮ A new upper bound for the multiple knapsack problem ⋮ Exact algorithms for solving the constrained parallel-machine scheduling problems with divisible processing times and penalties ⋮ Scheduling equal-length jobs with arbitrary sizes on uniform parallel batch machines ⋮ When greedy gives optimal: a unified approach ⋮ The constrained parallel-machine scheduling problem with divisible processing times and penalties

Cites Work

• A polynomial-time algorithm for knapsack with divisible item sizes
• Solving sequential knapsack problems
• Integer knapsack and flow covers with divisible coefficients: Polyhedra, optimization and separation
• The cutting stock problem and integer rounding
• The Sequential Knapsack Polytope

This page was built for publication: A polynomial algorithm for the multiple knapsack problem with divisible item sizes