Prof. Dr. Günter Rote | Freie Universität Berlin, Deutschland | Thursday, 19 September 2019 | 11:00 a.m. | N.2.01
For a given sequence of n numbers, we want to find a monotonically in- creasing 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 run- ning 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.