INTEGER ISOTONE OPTIMIZATION

Consider the following integer isotone optimization problem. Given an n-vector x find an n-vector y with integer components so as to minimiz e max{w(j)\x(j) - y(j)\ : 1 less than or equal to j less than or equal to n} subject to y(1) less than or equal to y(2) less than or equal t o ... less than or equal to y(n), where each weight w(j) > 0. In this article, the dual of this problem is defined, a strong duality theorem is established, and the set of all optimal solutions is shown to be a ll monotonic integer vectors lying in a vector interval. In addition, algorithms are obtained for computation of optimal solutions having th e worst-case time complexity O(n(2)), when w(j) are arbitrary, and O(n ), when w(j) = 1 for all j. The problem considered is of isotonic regr ession type and has practical applications. for example, to estimation and curve fitting. It is also of independent mathematical interest. T he problem and the results can be easily extended to a partially order ed set.