A fast algorithm for the linear multiple-choice knapsack problem

DOI10.1016/0167-6377(84)90027-0MaRDI QIDQ800227zbMATH OpenOpenAlexFDO

Authors Stanisław Walukiewicz, Krzysztof Dudzinski

Publication date 1984

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

Full work available at URL https://doi.org/10.1016/0167-6377(84)90027-0

zbMATH Keywords

branch-and bound approachfast algorithmlinear multiple-choice knapsack problemmedian finding in ordered sets

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Special problems of linear programming (transportation, multi-index, data envelopment analysis, etc.) (90C08) Integer programming (90C10)

Recommendations

• scientific article; zbMATH DE number 3860891
• An O(n) algorithm for the linear multiple choice knapsack problem and related problems
• An O(n) algorithm for the multiple-choice knapsack linear program
• A Fast Approximation Scheme for the Multiple Knapsack Problem
• scientific article; zbMATH DE number 3889280
• The linear multiple choice knapsack problem
• A minimal algorithm for the multiple-choice knapsack problem
• An exact algorithm for large multiple knapsack problems
• A branch and bound algorithm for solving the multiple-choice knapsack problem
• An efficient algorithm for multi-dimensional nonlinear knapsack problems

Cites work

• A note on the knapsack problem with special ordered sets
• An Algorithm for Large Zero-One Knapsack Problems
• An O(n) algorithm for the multiple-choice knapsack linear program
• On the computational power of pushdown automata
• The complexity of selection and ranking in X+Y and matrices with sorted columns
• The Linear Multiple Choice Knapsack Problem
• The Multiple-Choice Knapsack Problem

Cited in

(19)

• Exact methods for the knapsack problem and its generalizations
• Relaxation heuristics for a generalized assignment problem
• A minimal algorithm for the multiple-choice knapsack problem
• A branch \& bound algorithm for the 0-1 mixed integer knapsack problem with linear multiple choice constraints
• A comparison of Lagrangean and surrogate relaxations for the maximal covering location problem
• Lagrangean/surrogate relaxation for generalized assignment problems
• The linear multiple choice knapsack problem
• A linear-time algorithm for solving continuous maximin knapsack problems
• A Fast Approximation Scheme for the Multiple Knapsack Problem
• scientific article; zbMATH DE number 3889280 (Why is no real title available?)
• An O(n) algorithm for the multiple-choice knapsack linear program
• scientific article; zbMATH DE number 3860891 (Why is no real title available?)
• scientific article; zbMATH DE number 794382 (Why is no real title available?)
• Linear Time Algorithms for Knapsack Problems with Bounded Weights
• A multi-criteria approach to approximate solution of multiple-choice knapsack problem
• A branch and bound algorithm for solving the multiple-choice knapsack problem
• An O(n) algorithm for the linear multiple choice knapsack problem and related problems
• A dynamic programming approach to solving the multiple choice knapsack problem
• The linking set problem: a polynomial special case of the multiple-choice knapsack problem

This page was built for publication: A fast algorithm for the linear multiple-choice knapsack problem

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