License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/OASIcs.SOSA.2019.1
URN: urn:nbn:de:0030-drops-100274
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/10027/
Rote, Günter
Isotonic Regression by Dynamic Programming
Abstract
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.
BibTeX - Entry
@InProceedings{rote:OASIcs:2018:10027,
author = {G{\"u}nter Rote},
title = {{Isotonic Regression by Dynamic Programming}},
booktitle = {2nd Symposium on Simplicity in Algorithms (SOSA 2019)},
pages = {1:1--1:18},
series = {OpenAccess Series in Informatics (OASIcs)},
ISBN = {978-3-95977-099-6},
ISSN = {2190-6807},
year = {2018},
volume = {69},
editor = {Jeremy T. Fineman and Michael Mitzenmacher},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/10027},
URN = {urn:nbn:de:0030-drops-100274},
doi = {10.4230/OASIcs.SOSA.2019.1},
annote = {Keywords: Convex functions, dynamic programming, convex hull, isotonic regression}
}
Keywords: |
|
Convex functions, dynamic programming, convex hull, isotonic regression |
Collection: |
|
2nd Symposium on Simplicity in Algorithms (SOSA 2019) |
Issue Date: |
|
2018 |
Date of publication: |
|
08.01.2019 |