A linear-time algorithm for solving continuous maximin knapsack problems (Q2277359)

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)].