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. This paper shows 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. The paper also analyzes the computational complexity of the algorithm and discusses its significance from the standpoint of linear programming theory.