A polynomially solvable special case of the unbounded knapsack problem

DOI10.1016/S0167-6377(01)00076-1zbMath0981.90062WikidataQ127343667 ScholiaQ127343667MaRDI QIDQ5949903

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

Publication date: 5 December 2001

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

zbMATH Keywords

integer programmingcombinatorial optimizationpolynomial time algorithmknapsackcomputatioal complexity

Mathematics Subject Classification ID

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

Related Items

The skiving stock problem as a counterpart of the cutting stock problem ⋮ A new lower bound for the linear knapsack problem with general integer variables ⋮ When greedy gives optimal: a unified approach ⋮ A constructive periodicity bound for the unbounded knapsack problem ⋮ Unbounded knapsack problems with arithmetic weight sequences ⋮ A well-solvable special case of the bounded knapsack problem ⋮ The LM-Cut Heuristic Family for Optimal Numeric Planning with Simple Conditions

Cites Work

• Unnamed Item
• Unnamed Item
• Integer Programming with a Fixed Number of Variables
• Maximizing Submodular Set Functions: Formulations and Analysis of Algorithms
• When the Greedy Solution Solves a Class of Knapsack Problems
• Technical Note—Optimality of a Heuristic Solution for a Class of Knapsack Problems

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