A linear-time algorithm for solving continuous maximin knapsack problems

DOI10.1016/0167-6377(91)90082-ZzbMath0725.90066OpenAlexW2014181360MaRDI QIDQ2277359

Takahito Kuno, Hiroshi Konno, Eitan Zemel

Publication date: 1991

Published in: Operations Research Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0167-6377(91)90082-z

zbMATH Keywords

continuous knapsack problembinary searchlinear-time algorithmlinear maximin problemparametric variable elimination method

Mathematics Subject Classification ID

Abstract computational complexity for mathematical programming problems (90C60) Linear programming (90C05) Special problems of linear programming (transportation, multi-index, data envelopment analysis, etc.) (90C08) Existence of solutions for minimax problems (49J35) Computational methods for problems pertaining to operations research and mathematical programming (90-08)

Related Items

Relaxation-based algorithms for minimax optimization problems with resource allocation applications, A pegging approach to the precedence-constrained knapsack problem, Sensitivity analysis of the Knapsack sharing problem: perturbation of the weight of an item, Heuristic and reduction algorithms for the knapsack sharing problem, New upper bounds and exact methods for the knapsack sharing problem, Sensitivity analysis of the knapsack sharing problem: perturbation of the profit of an item, Nature plays with dice - terrorists do not: Allocating resources to counter strategic versus probabilistic risks, An exact algorithm for the knapsack sharing problem, An exact algorithm for the knapsack sharing problem with common items

Cites Work

• Unnamed Item
• An O(n) algorithm for the linear multiple choice knapsack problem and related problems
• Minimax linear programming problem
• A linear time randomizing algorithm for searching ranked functions
• Continuous maximin knapsack problems with GLB constraints
• An O(n) algorithm for the multiple-choice knapsack linear program
• Applying Parallel Computation Algorithms in the Design of Serial Algorithms
• Combinatorial Optimization with Rational Objective Functions
• The Linear Multiple Choice Knapsack Problem
• An Algorithm for Large Zero-One Knapsack Problems
• Linear max-min programming
• Selecting the Kth Element in $X + Y$ and $X_1 + X_2 + \cdots + X_m $
• A mofified gub algorithm for solving linear minimax problems
• Application of Programs with Maximin Objective Functions to Problems of Optimal Resource Allocation
• A Branch Search Algorithm for the Knapsack Problem