Algorithms for a class of isotonic regression problems

The isotonic regression problem has applications in statistics, operations research, and image processing. In this paper a general framework for the i sotonic regression algorithm is proposed. Under this framework, we discuss the isotonic regression problem in the case where the directed graph specif ying the order restriction is a directed tree with n vertices. A new algori thm is presented for this case, which can be regarded as a generalization o f the PAV algorithm of Ayer et al. Using a simple tree structure such as th e binomial heap, the algorithm can be implemented in O(n log n) time, impro ving the previously best known O(n(2)) time algorithm. We also present line ar time algorithms for special cases where the directed graph is a path or a star.