An O(n) algorithm for the multiple-choice knapsack linear program

DOI10.1007/BF02591729zbMath0532.90068DBLPjournals/mp/Dyer84WikidataQ56324187 ScholiaQ56324187MaRDI QIDQ3315277

Martin Dyer

Publication date: 1984

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

zbMATH Keywords

computational complexityanalysis of algorithmsmultiple choice knapsack problemlinear algorithm

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Numerical mathematical programming methods (65K05) Linear programming (90C05) Special problems of linear programming (transportation, multi-index, data envelopment analysis, etc.) (90C08)

Related Items (35)

Exact methods for the knapsack problem and its generalizations ⋮ A new Lagrangian relaxation approach to the generalized assignment problem ⋮ Minimizing the weighted number of tardy jobs on parallel processors ⋮ Measuring the power of soft correlated equilibrium in 2-facility simple non-increasing linear congestion games ⋮ Minimizing the weighted number of tardy jobs on a single machine with release dates ⋮ Exact approaches for the knapsack problem with setups ⋮ Multiple-choice knapsack constraint in graphical models ⋮ A minimal algorithm for the multiple-choice knapsack problem ⋮ A class of nonlinear nonseparable continuous Knapsack and multiple-choice knapsack problems ⋮ A dual approach for the continuous collapsing knapsack problem ⋮ Minimizing the weighted number of tardy jobs on a two-machine flow shop. ⋮ Optimal sequential inspection policies ⋮ A branch \& bound algorithm for the 0-1 mixed integer knapsack problem with linear multiple choice constraints ⋮ SALSA: combining branch-and-bound with dynamic programming to smoothen workloads in simple assembly line balancing ⋮ Linear time algorithms for some separable quadratic programming problems ⋮ An optimal randomized algorithm for \(d\)-variate zonoid depth ⋮ Minmax linear knapsack problem with grouped variables and gub ⋮ Budgeting with bounded multiple-choice constraints. ⋮ Continuous maximin knapsack problems with GLB constraints ⋮ Generalized correlated equilibrium for two-person games in extensive form with perfect information ⋮ A linear-time algorithm for solving continuous maximin knapsack problems ⋮ A multi-criteria approach to approximate solution of multiple-choice knapsack problem ⋮ A new combinatorial branch-and-bound algorithm for the knapsack problem with conflicts ⋮ A faster polynomial algorithm for the unbalanced Hitchcock transportation problem ⋮ Lagrangean/surrogate relaxation for generalized assignment problems ⋮ LP relaxation of the two dimensional knapsack problem with box and GUB constraints ⋮ Deriving expected values from probabilities of fuzzy subsets ⋮ An O(n) algorithm for the linear multiple choice knapsack problem and related problems ⋮ Relaxation heuristics for a generalized assignment problem ⋮ The linear multiple choice knapsack problem ⋮ New pseudopolynomial complexity bounds for the bounded and other integer knapsack related problems ⋮ Worst-case analysis of the greedy algorithm for a generalization of the maximum \(p\)-facility location problem ⋮ A linear-time algorithm for the bottleneck transportation problem with a fixed number of sources ⋮ A fast algorithm for the linear multiple-choice knapsack problem ⋮ The capacity expansion problem in the service industry

Cites Work

• Unnamed Item
• A o(n logn) algorithm for LP knapsacks with GUB constraints
• The Linear Multiple Choice Knapsack Problem
• An Algorithm for Large Zero-One Knapsack Problems
• THE MULTIPLE-CHOICE KNAPSACK PROBLEM
• The Multiple-Choice Knapsack Problem
• Convex Analysis

This page was built for publication: An O(n) algorithm for the multiple-choice knapsack linear program