Lipschitz Unimodal and Isotonic Regression on Paths and Trees
From MaRDI portal
Publication:3557035
DOI10.1007/978-3-642-12200-2_34zbMATH Open1283.68267arXiv0912.5182OpenAlexW1764007391MaRDI QIDQ3557035FDOQ3557035
Bardia Sadri, Jeff M. Phillips, Pankaj K. Agarwal
Publication date: 27 April 2010
Published in: LATIN 2010: Theoretical Informatics (Search for Journal in Brave)
Abstract: We describe algorithms for finding the regression of t, a sequence of values, to the closest sequence s by mean squared error, so that s is always increasing (isotonicity) and so the values of two consecutive points do not increase by too much (Lipschitz). The isotonicity constraint can be replaced with a unimodular constraint, where there is exactly one local maximum in s. These algorithm are generalized from sequences of values to trees of values. For each scenario we describe near-linear time algorithms.
Full work available at URL: https://arxiv.org/abs/0912.5182
Graph theory (including graph drawing) in computer science (68R10) Data structures (68P05) Nonnumerical algorithms (68W05)
Cited In (1)
This page was built for publication: Lipschitz Unimodal and Isotonic Regression on Paths and Trees
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3557035)
