An algorithm for a separable integer programming problem with cumulatively bounded variables

An algorithm is presented for obtaining the optimal solution of an integer programming problem in which the nested constraints represent the cumulative bounding of the variables and the objective function is a sum of concave functions of one variables. The algorithm requires O(m log(m)log²(b_m/m)) time, where m is the number of variables and b_m is an upper bound on the sum of the m variables, b_m ⩾m⩾1. It is also demonstrated that a special case of identical concave functions is solvable in O(m). Both results significantly improve the previous bounds for these problems.