Algorithms for a Class of Isotonic Regression Problems |
| |
| Authors: | P M Pardalos G Xue |
| |
| Affiliation: | (1) Department of Industrial and Systems Engineering, 303 Weil Hall, University of Florida, Gainesville, FL 32611, USA. pardalos@ufl.edu., US;(2) Department of Computer Science, The University of Vermont, Burlington, VT 05405, USA. xue@cs.uvm.edu., US |
| |
| 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.
Received September 2, 1997; revised January 2, 1998, and February 16, 1998. |
| |
| Keywords: | , Isotonic regression, Binomial heap, Linear time algorithms, |
| 本文献已被 SpringerLink 等数据库收录！ |
|
