A dynamic programming approach to segmented isotonic regression

Víctor Bucarey; Martine Labbé; Juan Morales; Salvador Pineda

doi:10.1016/j.omega.2021.102516

Journal articles

A dynamic programming approach to segmented isotonic regression

Víctor Bucarey ¹ Martine Labbé ^{2, 3} Juan Morales ^{4, *} Salvador Pineda ⁵

* Corresponding author

1 Data Analytics Laboratory

2 INOCS - Integrated Optimization with Complex Structure

Inria Lille - Nord Europe, ULB - Université libre de Bruxelles, CRIStAL - Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189

3 Département d'informatique [Bruxelles]

4 Department of Applied Mathematics

5 Department of Electrical Engineering

Abstract : This paper proposes a polynomial-time algorithm to construct the monotone stepwise curve that minimizes the sum of squared errors with respect to a given cloud of data points. The fitted curve is also constrained on the maximum number of steps it can be composed of and on the minimum step length.

Keywords : Cardinality-constrained shortest path problem isotonic regression segmented regression inverse optimization data clustering consumers' price-response

Document type :

Journal articles

Domain :

Computer Science [cs] / Operations Research [cs.RO]

Complete list of metadata

https://hal.inria.fr/hal-03046338
Contributor : Martine Labbé Connect in order to contact the contributor
Submitted on : Tuesday, December 8, 2020 - 1:27:43 PM
Last modification on : Friday, January 21, 2022 - 3:10:23 AM
Long-term archiving on: : Tuesday, March 9, 2021 - 7:20:37 PM

A dynamic programming approach to segmented isotonic regression

File

Identifiers

Collections

Citation

Export

Metrics

Contact Legal Notice Personal Data

A dynamic programming approach to segmented isotonic regression

File

Identifiers

Collections

Citation

Export

Share

Metrics

Contact Legal Notice Personal Data