A well-solvable special case of the bounded knapsack problem

DOI10.1016/J.ORL.2011.01.006MaRDI QIDQ2275577zbMATH OpenOpenAlexFDO

Authors Vladimir G. Deineko, Gerhard J. Woeginger

Publication date 9 August 2011

Published in Operations Research Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.orl.2011.01.006

zbMATH Keywords

combinatorial optimizationcomputational complexitycross ratio orderedpolynomial time algorithm

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Abstract computational complexity for mathematical programming problems (90C60)

Recommendations

• A polynomially solvable special case of the unbounded knapsack problem
• scientific article; zbMATH DE number 4031399
• The knapsack problem with generalized upper bounds
• Optimal strategy for solving a special case of the knapsack problem by the branch and bound method
• A solution procedure for general knapsack problems with a few constraints
• A minimal algorithm for the bounded knapsack problem
• A Minimal Algorithm for the Bounded Knapsack Problem
• Bounds for nested knapsack problems
• The knapsack problem with special neighbor constraints
• Exact solution of a class of nonlinear knapsack problems

Cites work

• A polynomial-time algorithm for knapsack with divisible item sizes
• A polynomially solvable special case of the unbounded knapsack problem
• scientific article; zbMATH DE number 44282 (Why is no real title available?)
• scientific article; zbMATH DE number 3571502 (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)

• Using well-solvable minimum cost exact covering for VLSI clock energy minimization
• Knapsack problems -- an overview of recent advances. I: Single knapsack problems
• Optimal strategy for solving a special case of the knapsack problem by the branch and bound method
• A polynomial-time algorithm for knapsack with divisible item sizes
• Unbounded knapsack problems with arithmetic weight sequences
• A polynomially solvable special case of the unbounded knapsack problem
• Bilevel optimization for the deployment of refuelling stations for electric vehicles on road networks
• Online unbounded knapsack

This page was built for publication: A well-solvable special case of the bounded knapsack problem

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