An O(n) algorithm for the linear multiple choice knapsack problem and related problems (Q761347)

The following linear programming problem is studied: \[ (P):\quad Maximize\quad \sum_{j\in N}c_ jx_ j, \] \[ subject\quad to\quad \sum_{j\in N}a_ jx_ j=a_ 0,\quad \sum_{j\in J_ k}b_ jx_ j=b^ k_ 0\quad for\quad k=1,...,r,\quad x_ j\geq 0\quad for\quad j\in N; \] all \(J_ k\) are supposed to be mutually disjoint, \(a_ 0\) and all \(b^ k_ 0\) are nonnegative and the \(b_ j\) are nonzero. Among others problem (P) generalizes the linear knapsack problem as well as the multiple choice knapsack problem. For the solution of (P) an O(n)- algorithm is presented, which is based on Megiddo's algorithm for linear programming [see \textit{N. Megiddo}, SIAM J. Comput. 12, 347-353 (1983; Zbl 0532.90061)]. Since the algorithm presented relies on convexity rather than linearity of the functions involved it provides at the same time an O(n)-algorithm for a nonlinear analogue of (D), the linear programming dual of (P), having various applications in location theory.