A dual approach for the continuous collapsing knapsack problem

DOI10.1007/BF02592953zbMath0637.90067MaRDI QIDQ3778543

Marc E. Posner, Hisatoshi Suzuki

Publication date: 1987

Published in: Mathematical Programming (Search for Journal in Brave)

zbMATH Keywords

geometric approachdualityOptimality conditionscontinuous collapsing knapsack problem

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Integer programming (90C10) Linear programming (90C05)

Cites Work

• An O(n) algorithm for the linear multiple choice knapsack problem and related problems
• An exact algorithm for the 0-1 collapsing knapsack problem
• An efficient algorithm for determining the convex hull of a finite planar set
• An O(n) algorithm for the multiple-choice knapsack linear program
• The continuous collapsing Knapsack problem
• A o(n logn) algorithm for LP knapsacks with GUB constraints
• APPROXIMATE ALGORITHMS FOR THE MULTIPLE-CHOICE CONTINUOUS KNAPSACK PROBLEMS
• The Linear Multiple Choice Knapsack Problem
• Convex hulls of finite sets of points in two and three dimensions
• THE MULTIPLE-CHOICE KNAPSACK PROBLEM
• Implicit representation of generalized variable upper bounds in linear programming
• The Collapsing 0–1 Knapsack Problem
• The Multiple-Choice Knapsack Problem

This page was built for publication: A dual approach for the continuous collapsing knapsack problem