Lipschitz unimodal and isotonic regression on paths and trees


Journal Article

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, for exactly one local maximum in s. These algorithm are generalized from sequences of values to trees of values. For each we describe near-linear time algorithms. © 2010 Springer-Verlag.

Full Text

Duke Authors

Cited Authors

  • Agarwal, PK; Phillips, JM; Sadri, B

Published Date

  • June 18, 2010

Published In

Volume / Issue

  • 6034 LNCS /

Start / End Page

  • 384 - 396

Electronic International Standard Serial Number (EISSN)

  • 1611-3349

International Standard Serial Number (ISSN)

  • 0302-9743

Digital Object Identifier (DOI)

  • 10.1007/978-3-642-12200-2_34

Citation Source

  • Scopus