Article ID: | iaor199544 |
Country: | Netherlands |
Volume: | 47 |
Issue: | 3 |
Start Page Number: | 251 |
End Page Number: | 261 |
Publication Date: | Dec 1993 |
Journal: | Discrete Applied Mathematics |
Authors: | Tamir A., Kaufman Y. |
Keywords: | programming: mathematical |
Isotonic regression models have been used extensively with various objective functions. In this paper the authors consider the isotonic regression model with the minmax criterion. The model is presented and interpreted as a multi-center location problem on the real line, with precedence constraints on the locations of the centers. Viewed as a location problem, this model generalizes the classical (weighted) 1-center problem on the line. The authors obtain an explicit expression for the optimal objective value, and use it to develop an efficient subquadratic algorithm for solving the problem. Finally they present and discuss a generalization which unifies the above model and other location problems with distance constraints.