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

DOI10.1007/BF01919085MaRDI QIDQ3312019zbMATH OpenOpenAlexFDO

Authors 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

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

Cites work

• scientific article; zbMATH DE number 3668317 (Why is no real title available?)
• A o(n logn) algorithm for LP knapsacks with GUB constraints
• An Algorithm for Large Zero-One Knapsack Problems
• Combinatorial Optimization with Rational Objective Functions
• Linear-Time Algorithms for Linear Programming in $R^3 $ and Related Problems
• Selecting the Kth Element in $X + Y$ and $X_1 + X_2 + \cdots + X_m $
• The Linear Multiple Choice Knapsack Problem
• The Multiple-Choice Knapsack Problem

Cited in

(2)

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

This page was built for publication: AnO (n)-algorithm for LP-knapsacks with a fixed number of GUB constraints

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