New pseudopolynomial complexity bounds for the bounded and other integer knapsack related problems

DOI10.1016/j.orl.2009.05.003zbMath1173.90523OpenAlexW1974761916MaRDI QIDQ1038094

Arie Tamir

Publication date: 17 November 2009

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

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

zbMATH Keywords

bounded knapsack problembounded multiple-choice knapsack problemmulticover problempseudopolynomial algorithms

Mathematics Subject Classification ID

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

Related Items

Knapsack problems -- an overview of recent advances. I: Single knapsack problems, Determining the \(K\)-best solutions of knapsack problems, On probabilistic algorithm for solving almost all instances of the set partition problem, Scaling, proximity, and optimization of integrally convex functions, Unnamed Item, Tight bounds for periodicity theorems on the unbounded knapsack problem, A constructive periodicity bound for the unbounded knapsack problem, More on change-making and related problems

Uses Software

• Knapsack

Cites Work

• Unnamed Item
• An O(n) algorithm for the linear multiple choice knapsack problem and related problems
• Cyclical scheduling and multi-shift scheduling: complexity and approximation algorithms
• Heuristic algorithms for the multiple knapsack problem
• The relationship between integer and real solutions of constrained convex programming
• Dynamic programming revisited: Improving knapsack algorithms
• A Strongly Polynomial Algorithm to Solve Combinatorial Linear Programs
• An O(n) algorithm for the multiple-choice knapsack linear program
• Applying Parallel Computation Algorithms in the Design of Serial Algorithms
• Sensitivity theorems in integer linear programming
• An Algorithm for Large Zero-One Knapsack Problems
• Slowing down sorting networks to obtain faster sorting algorithms
• The interval subset sum problem
• Linear Time Algorithms for Knapsack Problems with Bounded Weights
• Convex separable optimization is not much harder than linear optimization
• Budgeting with bounded multiple-choice constraints.