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

The authors analyze the problem \[ P_{(p,s)}: \max \sum^{s}_{i=p}f_ i(x_ i)\quad s.t.\quad \sum^{j}_{i=p}x_ i\leq b_ j\quad (j=p,...,s) \] with \[ x_ i\in X_ i:=\{0,1,2,...,b_ i\},\quad f_ i\text{ non-decreasing and concave on \(X_ i,\) and \(0\leq b_ p\leq...\leq b_ j\) with }b_ s\geq s. \] First a sufficient condition under which an optimal solution to a Lagrangian relaxation also yields an optimal solution to \(P_{(1,m)}\) is developed. Secondly an incremental (but pseudo-polynomial) algorithm (``greedy'') is given which constructs the lexicographically largest optimal solution to \(P_{(p,s)}\) in \(O(m\cdot b_ m)\) time, where \(b_ m\) is an upper bound on the sum of all variables. By recursively solving \(P(1,\lfloor m/2\rfloor)\), using the monotonicity of the lexicographically largest optimal solution (in s) and a divide- and-conquer approach the authors get a recurrence relation for this refined algorithm (``quicker greedy'') which solves P(1,m) in O(m log(m)\(\cdot \log^ 2(b_ m/m))\) time - where each function evaluation \(f_ i(x_ i)\) counts by one. In the special case where \(f_ j=f\) \((j=1,...,m)\) the sufficient condition can be strengthened and this allows an O(m) time algorithm - where additionally the floor function evaluations \(\lceil y_ j\rceil\) resp. \(\lfloor y_ j\rfloor\) count by one, too.