A linear-time algorithm for solving continuous maximin knapsack problems
binary searchcontinuous knapsack problemlinear maximin problemlinear-time algorithmparametric variable elimination method
Existence of solutions for minimax problems (49J35) Computational methods for problems pertaining to operations research and mathematical programming (90-08) Linear programming (90C05) Special problems of linear programming (transportation, multi-index, data envelopment analysis, etc.) (90C08) Abstract computational complexity for mathematical programming problems (90C60)
The paper deals with the linear maximin problem \[ (KP)\text{ maximize } z=\min_{i\in M}\{\sum_{j\in J_ i}c_ jx_ j\} \] subject to \(\sum_{j\in N}a_ jx_ j\leq b\), \(0\leq x_ j\leq 1\), \(j\in N\), where \(M=\{1,...,m\}\), \(N=\{1,...,n\}\), \(J_ p\cap J_ q=\emptyset\), \(p\neq q\), and \(\cup_{i\in M}J_ i\subset N\). An O(n) algorithm for solving (KP) is described, which is based on the parametric (variable elimination) method of \textit{N. Megiddo} [Math. Oper. Res. 4, 414-424 (1979; Zbl 0425.90076); and J. Assoc. Comput. Mach. 30, 852-865 (1983; Zbl 0627.68034)].
- On linear-time algorithms for the continuous quadratic Knapsack problem
- An Efficient Method for a Class of Continuous Nonlinear Knapsack Problems
- An algorithm for the continuous variable upper bound knapsack problem
- Linear Time Algorithms for Knapsack Problems with Bounded Weights
- An exact algorithm for the 0-1 linear knapsack problem with a single continuous variable
- scientific article; zbMATH DE number 6263683
- Constant-time approximation algorithms for the knapsack problem
- A fast algorithm for the linear multiple-choice knapsack problem
- Continuous maximin knapsack problems with GLB constraints
- An O(n) algorithm for the linear multiple choice knapsack problem and related problems
- A Branch Search Algorithm for the Knapsack Problem
- A linear time randomizing algorithm for searching ranked functions
- A mofified gub algorithm for solving linear minimax problems
- An Algorithm for Large Zero-One Knapsack Problems
- An O(n) algorithm for the linear multiple choice knapsack problem and related problems
- An O(n) algorithm for the multiple-choice knapsack linear program
- Application of Programs with Maximin Objective Functions to Problems of Optimal Resource Allocation
- Applying Parallel Computation Algorithms in the Design of Serial Algorithms
- Combinatorial Optimization with Rational Objective Functions
- Continuous maximin knapsack problems with GLB constraints
- scientific article; zbMATH DE number 3511563 (Why is no real title available?)
- Linear max-min programming
- Minimax linear programming problem
- Selecting the Kth Element in $X + Y$ and $X_1 + X_2 + \cdots + X_m $
- The Linear Multiple Choice Knapsack Problem
- An algorithm for solving a structured class of linear programming problems
- Relaxation-based algorithms for minimax optimization problems with resource allocation applications
- Heuristic and reduction algorithms for the knapsack sharing problem
- A pegging approach to the precedence-constrained knapsack problem
- Sensitivity analysis of the Knapsack sharing problem: perturbation of the weight of an item
- New upper bounds and exact methods for the knapsack sharing problem
- An exact algorithm for the knapsack sharing problem
- On the complexity of the continuous unbounded knapsack problem with uncertain coefficients
- Continuous maximin knapsack problems with GLB constraints
- scientific article; zbMATH DE number 6836465 (Why is no real title available?)
- Sensitivity analysis of the knapsack sharing problem: perturbation of the profit of an item
- Linear Time Algorithms for Knapsack Problems with Bounded Weights
- scientific article; zbMATH DE number 6263683 (Why is no real title available?)
- Max-max, max-min, min-max and min-min knapsack problems with a parametric constraint
- An exact algorithm for the 0-1 linear knapsack problem with a single continuous variable
- An exact algorithm for the knapsack sharing problem with common items
- Nature plays with dice - terrorists do not: Allocating resources to counter strategic versus probabilistic risks
This page was built for publication: A linear-time algorithm for solving continuous maximin knapsack problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2277359)
