文章基本信息

标题：Isotonic Regression by Dynamic Programming
本地全文：下载
作者：G{"u}nter Rote
期刊名称：OASIcs : OpenAccess Series in Informatics
电子版ISSN：2190-6807
出版年度：2018
卷号：69
页码：1-18
DOI：10.4230/OASIcs.SOSA.2019.1
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：For a given sequence of 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.
关键词：Convex functions; dynamic programming; convex hull; isotonic regression