Mj. Best et Ry. Tan, AN O(N(3)LOG N) STRONG POLYNOMIAL ALGORITHM FOR AN ISOTONIC REGRESSION KNAPSACK-PROBLEM, Journal of optimization theory and applications, 79(3), 1993, pp. 463-478
Citations number
4
Categorie Soggetti
Operatione Research & Management Science",Mathematics,"Operatione Research & Management Science
We introduce the isotonic regression knapsack problem [GRAPHICS] where
each di is positive and each alpha(i), a(i), i = 1,...,n, and c are a
rbitrary scalars. This problem is the natural extension of the isotoni
c regression problem which permits a strong polynomial solution algori
thm. In this paper, an approach is developed from the Karush-Kuhn-Tuck
er conditions. By considering the Lagrange function without the inequa
lities, we establish a way to find the proper Lagrange multiplier asso
ciated with the equation using a parametric program, which yields opti
mality. We show that such a procedure can be performed in strong polyn
omial time, and an example is demonstrated.