ISSN:
1432-0541
Keywords:
Key words. Isotonic regression, Binomial heap, Linear time algorithms.
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
,
Mathematics
Notes:
Abstract. The isotonic regression problem has applications in statistics, operations research, and image processing. In this paper a general framework for the isotonic regression algorithm is proposed. Under this framework, we discuss the isotonic regression problem in the case where the directed graph specifying the order restriction is a directed tree with n vertices. A new algorithm is presented for this case, which can be regarded as a generalization of the PAV algorithm of Ayer et al. Using a simple tree structure such as the binomial heap, the algorithm can be implemented in O(n log n) time, improving the previously best known O(n 2 ) time algorithm. We also present linear time algorithms for special cases where the directed graph is a path or a star.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/PL00009258
Permalink