A polynomially solvable special case of the unbounded knapsack problem

DOI10.1016/S0167-6377(01)00076-1MaRDI QIDQ5949903zbMATH OpenWikidataFDO

Authors Moshe Zukerman, Long Jia, Timothy Neame, Gerhard J. Woeginger

Publication date 5 December 2001

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

Full work available at URL https://doi.org/10.1016/S0167-6377(01)00076-1

zbMATH Keywords

combinatorial optimizationcomputatioal complexityinteger programmingknapsackpolynomial time algorithm

Mathematics Subject Classification ID

Complexity and performance of numerical algorithms (65Y20) Integer programming (90C10) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57)

Recommendations

• A well-solvable special case of the bounded knapsack problem
• Unbounded knapsack problems with arithmetic weight sequences
• A polynomial-time algorithm for knapsack with divisible item sizes
• The unbounded knapsack problem
• scientific article; zbMATH DE number 3876925

Cites work

• 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 Programming with a Fixed Number of Variables
• Maximizing Submodular Set Functions: Formulations and Analysis of Algorithms
• Technical Note—Optimality of a Heuristic Solution for a Class of Knapsack Problems
• When the Greedy Solution Solves a Class of Knapsack Problems

Cited in

(10)

• A constructive periodicity bound for the unbounded knapsack problem
• A well-solvable special case of the bounded knapsack problem
• A polynomial-time algorithm for knapsack with divisible item sizes
• scientific article; zbMATH DE number 7401920 (Why is no real title available?)
• The skiving stock problem as a counterpart of the cutting stock problem
• Unbounded knapsack problems with arithmetic weight sequences
• The LM-Cut Heuristic Family for Optimal Numeric Planning with Simple Conditions
• When greedy gives optimal: a unified approach
• Online unbounded knapsack
• A new lower bound for the linear knapsack problem with general integer variables

This page was built for publication: A polynomially solvable special case of the unbounded knapsack problem

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