Correctness of Kruskal's Algorithms for Monotone Regression with Ties

Kruskal has proposed two modifications of monotone regression that can be applied if there are ties in nonmetric scaling data. In this note we prove Kruskal's conjecture that his algorithms give the optimal least squares solution of these modified monotone regression problems. We also propose another (third) approach for dealing with ties.