The Knapsack Sharing Problem

The knapsack sharing problem has a utility or tradeoff function for each variable and seeks to maximize the value of the smallest tradeoff function (a maximin objective function). A single constraint places an upper bound on the sum of the non-negative variables. We develop efficient algorithms for piecewise linear, nonlinear, and piecewise nonlinear tradeoff functions and for any knapsack sharing problem with integer variables. These algorithms for the knapsack sharing problem extend the sharing problem algorithm in a companion paper to any piecewise linear, nonlinear, or piecewise nonlinear tradeoff functions.