Unbounded knapsack problems with arithmetic weight sequences

DOI10.1016/J.EJOR.2011.03.028MaRDI QIDQ545110zbMATH OpenOpenAlexFDO

Authors Gerhard J. Woeginger, Vladimir G. Deineko

Publication date 22 June 2011

Published in European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ejor.2011.03.028

zbMATH Keywords

computational complexitycombinatorial optimizationdynamic programmingpolynomially solvable special case

Mathematics Subject Classification ID

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

Recommendations

• A polynomially solvable special case of the unbounded knapsack problem
• The unbounded knapsack problem
• A well-solvable special case of the bounded knapsack problem
• A polynomial-time algorithm for knapsack with divisible item sizes
• An exact algorithm for large unbounded knapsack problems

Cites work

• scientific article; zbMATH DE number 4089320 (Why is no real title available?)
• scientific article; zbMATH DE number 44282 (Why is no real title available?)
• A Polynomial-Time Algorithm for the Knapsack Problem with Two Variables
• A linear algorithm for integer programming in the plane
• A new lower bound for the linear knapsack problem with general integer variables
• A polynomially solvable special case of the unbounded knapsack problem
• Integer Programming with a Fixed Number of Variables
• On linear forms whose coefficients are in arithmetic progression
• On variations of the subset sum problem
• When the Greedy Solution Solves a Class of Knapsack Problems

Cited in

(7)

• A polynomially solvable special case of the unbounded knapsack problem
• The unbounded knapsack problem
• A polynomial-time algorithm for knapsack with divisible item sizes
• Knapsack problems with position-dependent item weights or profits
• A constructive periodicity bound for the unbounded knapsack problem
• Tight bounds for periodicity theorems on the unbounded knapsack problem
• Knapsack problems -- an overview of recent advances. I: Single knapsack problems

This page was built for publication: Unbounded knapsack problems with arithmetic weight sequences

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