## 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
### Abstract

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.

Last update: November 9, 2018.