Efficient computation of an isotonic median regression Original Research Article

The isotonic median regression problem arises from statistics. An algorithm, the PAV algorithm, has been proposed for solving this problem since 1980. In this paper, we propose two kinds of data structures for efficiently implementing the PAV algorithm. The running time of the algorithm is also improved.