Isotonic median regression for orders representable by rooted trees
针对统计中的等渗中位数回归问题，提出一个时间复杂度为O(mn)的简单算法，适用于可表示为有根树的序，并通过线性规划验证其最优性。
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. We present a simple algorithm, of time complexity O(mn), for calculating isotonic median regression for orders representable by rooted trees. We believe that this algorithm is the best currently available for this problem. The algorithm is validated by a linear programming approach which provides additional insight.