ON AN OPTIMIZATION PROBLEM WITH NESTED CONSTRAINTS

We describe algorithms for solving the integer programming problem maximise ∑ j=1 n{cauchy integral}j(xj),subject to ∑ jε{lunate}Sixj≤bi, i=1,...,m,xj≥0, j=1,...,n, where the {cauchy integral}i are concave nondecreasing and the Si form a nested collection of sets. For the general problem, we present an algorithm of time-complexity O(n log2 n log b), where b is less than the largest of the bi. We also examine the case in which all {cauchy integral}i are identical and give an algorithm requiring O(n + m log m) time. Both algorithms use only O(n) space. © 1990.