Fast, Provable Algorithms for Isotonic Regression in all l-norms

Given a directed acyclic graph G, and a set of values y on the vertices, the Isotonic Regression of y is a vector x that respects the partial order described by G, and minimizes x y, for a specified norm.