Günter Rote:

Isotonic regression by dynamic programming

In: Proceedings of the 2nd Symposium on Simplicity in Algorithms (SOSA 2019), San Diego, January 2019, Editors: Jeremy Fineman and Michael Mitzenmacher, OpenAccess Series in Informatics (OASIcs), Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2019, Vol. 69, pp. 1:1–1:18. doi:10.4230/OASIcs.SOSA.2019.1  →BibTeX


For a given sequence of n numbers, we want to find a monotonically increasing sequence of the same length that best approximates it in the sense of minimizing the weighted sum of absolute values of the differences. A conceptually easy dynamic programming approach leads to an algorithm with running time O(n log n). While other algorithms with the same running time are known, our algorithm is very simple. The only auxiliary data structure that it requires is a priority queue. The approach extends to other error measures.

  pdf file
other papers about this subject
Last update: November 9, 2018.