The isotonic median regression problem arising in statistics is as follows. We are given m observations falling into n sets, the ith set containing mi observations. The problem requires the determination of n real numbers, the ith being the value ‘fitted’ to each observation in the ith set. These n numbers chosen must satisfy certain (total or partial) order requirements and minimize the distance between the vectors of observed and fitted values in the l1 norm. A simple algorithm is presented, of time complexity O(mn), for calculating isotonic median regression for orders representable by rooted trees. It is believed that this algorithm is the best currently available for this problem. The algorithm is validated by a linear programming approach which provides additional insight.
