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

DOI10.1007/BF01919085zbMATH Open0529.90072OpenAlexW1963870270MaRDI QIDQ3312019FDOQ3312019

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

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

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)