Isotonic Median Regression: A Linear Programming Approach

The isotonic median regression problem arises in statistics. It is known that the isotonic median regression problem, with respect to a complete order, may be solved by a “Pool Adjacent Violators” algorithm. In this paper we show that this algorithm is a dual method for solving a linear programming formulation of the problem. The linear programming approach provides additional insight into the algorithm as well as a simple proof of its validity. We also analyze the computational complexity of the algorithm and discuss its significance from the standpoint of linear programming theory.