AnO (n)-algorithm for LP-knapsacks with a fixed number of GUB constraints

DOI10.1007/BF01919085zbMath0529.90072OpenAlexW1963870270MaRDI QIDQ3312019

Peter Brucker

Publication date: 1984

Published in: Zeitschrift für Operations Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01919085

zbMATH Keywords

parametric programminggeneralized upper boundslinear programming knapsack problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Integer programming (90C10) Linear programming (90C05)

Related Items

Exact methods for the knapsack problem and its generalizations ⋮ Minmax linear knapsack problem with grouped variables and gub

Cites Work

• Unnamed Item
• Linear-Time Algorithms for Linear Programming in $R^3 $ and Related Problems
• A o(n logn) algorithm for LP knapsacks with GUB constraints
• Combinatorial Optimization with Rational Objective Functions
• The Linear Multiple Choice Knapsack Problem
• An Algorithm for Large Zero-One Knapsack Problems
• Selecting the Kth Element in $X + Y$ and $X_1 + X_2 + \cdots + X_m $
• The Multiple-Choice Knapsack Problem