Efficient computation of an isotonic median regression (Q1893692)

We consider the following isotonic median regression problem (IMR): \[ \min \sum^ n_{i = 1} \sum^{m_ i}_{j = 1} | y_{ij} - x_ i |, \quad \text{s.t.} \quad x_ 1 \leq x_ 2 \leq \cdots \leq x_ n. \] The linear time median finding algorithm is not very practical and the linear programming approach to the IMR problem involves much overhead. More efficient implementation for the pooling adjacent violator (PAV) algorithm is desirable. We present two data structures for efficient implementation of the PAV algorithm. The first one uses balanced search trees and the second one uses merging.