A nonlinear Knapsack problem

The nonlinear Knapsack problem is to maximize a separable concave objective function, subject to a single ‘packing’ constraint, in nonnegative variables. the paper considers this problem in integer and continuous variables, and also when the packing constraint is convex. Although the nonlinear Knapsack problem appears difficult in comparison with the linear Knapsack problem, it proves that its complexity is similar. The paper demonstrates for the nonlinear Knapsack problem in n integer variables and kanpsack volume limit B, a fully polynomial approximation scheme with running time Õ((1/•²)(n+1/•²)) (omitting polylog terms); and for the continuous case an algorithm delivering an •-accurate solution in O(nlog(B/•)) operations.