An O(n) algorithm for the linear multiple choice knapsack problem and related problems

DOI10.1016/0020-0190(84)90014-0zbMath0555.90069OpenAlexW1965268014MaRDI QIDQ761347

Publication date: 1984

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(84)90014-0

zbMATH Keywords

location theory linear algorithms multiple choice knapsack problem least distance hyperplane linear knapsack problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Numerical mathematical programming methods (65K05) Linear programming (90C05) Inventory, storage, reservoirs (90B05)

Related Items (42)

Optimal deterministic and robust selection of electricity contracts ⋮ A new bound and an \(O(mn)\) algorithm for the undesirable 1-median problem (maxian) on networks ⋮ A new Lagrangian relaxation approach to the generalized assignment problem ⋮ Solving the linear multiple choice knapsack problem with two objectives: Profit and equity ⋮ Stop location design in public transportation networks: covering and accessibility objectives ⋮ On the planar piecewise quadratic 1-center problem ⋮ Exact approaches for the knapsack problem with setups ⋮ Multiple-choice knapsack constraint in graphical models ⋮ The nestedness property of location problems on the line ⋮ Revisiting \(k\)-sum optimization ⋮ A minimal algorithm for the multiple-choice knapsack problem ⋮ An algorithm for the polyhedral cycle cover problem with constraints on the number and length of cycles ⋮ A class of nonlinear nonseparable continuous Knapsack and multiple-choice knapsack problems ⋮ A dual approach for the continuous collapsing knapsack problem ⋮ Improved algorithms for several network location problems with equality measures. ⋮ Continuous location of dimensional structures. ⋮ Optimal sequential inspection policies ⋮ A branch \& bound algorithm for the 0-1 mixed integer knapsack problem with linear multiple choice constraints ⋮ A relative robust approach on expected returns with bounded CVaR for portfolio selection ⋮ 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. ⋮ A linear-time algorithm for solving continuous maximin knapsack problems ⋮ Computing the geodesic center of a simple polygon ⋮ 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 ⋮ Finding an Euclidean anti-\(k\)-centrum location of a set of points ⋮ A faster polynomial algorithm for the unbalanced Hitchcock transportation problem ⋮ Up- and downgrading the 1-center in a network ⋮ Optimal algorithms for the path/tree-shaped facility location problems in trees ⋮ Median hyperplanes in normed spaces -- a survey ⋮ The linear multiple choice knapsack problem ⋮ Generalized penalty for circular coordinate representation ⋮ New pseudopolynomial complexity bounds for the bounded and other integer knapsack related problems ⋮ Solving restricted line location problems via a dual interpretation ⋮ Worst-case analysis of the greedy algorithm for a generalization of the maximum \(p\)-facility location problem ⋮ One-way and round-trip center location problems ⋮ A linear-time algorithm for the bottleneck transportation problem with a fixed number of sources ⋮ Minimizing the sum of the \(k\) largest functions in linear time. ⋮ Locating a median line with partial coverage distance

Cites Work

This page was built for publication: An O(n) algorithm for the linear multiple choice knapsack problem and related problems