Minmax linear knapsack problem with grouped variables and gub

Abstract

Let be a partition of be a partition of Sⁱ and c_i and a_j are scalars for We consider the problem

MinimiseMaximum

Subject to

An algorithm is proposed to solve this problem. We also obtain a linear tune algorithm to solve the knapsack sharing problem with piece-wise linear trade-off functions which improves its existing time bound. As a by-product of this result, we have an O(n) algorithm to solve the continuous minmax knapsack problem with GLB constraints which improves the existing time bound

Keywords:

• Knapsack Problem
• Grouped Variables