A Seemingly Polynomial-Time Algorithm for Optimal Curve Fitting by Segmented Straight Lines

Research output: Chapter in Book/Report/Conference proceeding › Paper in conference proceeding

Standard

A Seemingly Polynomial-Time Algorithm for Optimal Curve Fitting by Segmented Straight Lines. / Troeng, Olof; Falt, Mattias.

2018 IEEE Conference on Decision and Control, CDC 2018. Vol. 2018-December Institute of Electrical and Electronics Engineers Inc., 2019. p. 4091-4096 8618654.

Research output: Chapter in Book/Report/Conference proceeding › Paper in conference proceeding

Harvard

Troeng, O & Falt, M 2019, A Seemingly Polynomial-Time Algorithm for Optimal Curve Fitting by Segmented Straight Lines. in 2018 IEEE Conference on Decision and Control, CDC 2018. vol. 2018-December, 8618654, Institute of Electrical and Electronics Engineers Inc., pp. 4091-4096, 57th IEEE Conference on Decision and Control, CDC 2018, Miami, United States, 2018/12/17. https://doi.org/10.1109/CDC.2018.8618654

APA

Troeng, O., & Falt, M. (2019). A Seemingly Polynomial-Time Algorithm for Optimal Curve Fitting by Segmented Straight Lines. In 2018 IEEE Conference on Decision and Control, CDC 2018 (Vol. 2018-December, pp. 4091-4096). [8618654] Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/CDC.2018.8618654

CBE

Troeng O, Falt M. 2019. A Seemingly Polynomial-Time Algorithm for Optimal Curve Fitting by Segmented Straight Lines. In 2018 IEEE Conference on Decision and Control, CDC 2018. Institute of Electrical and Electronics Engineers Inc. pp. 4091-4096. https://doi.org/10.1109/CDC.2018.8618654

MLA

Troeng, Olof and Mattias Falt "A Seemingly Polynomial-Time Algorithm for Optimal Curve Fitting by Segmented Straight Lines". 2018 IEEE Conference on Decision and Control, CDC 2018. Institute of Electrical and Electronics Engineers Inc. 2019, 4091-4096. https://doi.org/10.1109/CDC.2018.8618654

Vancouver

Troeng O, Falt M. A Seemingly Polynomial-Time Algorithm for Optimal Curve Fitting by Segmented Straight Lines. In 2018 IEEE Conference on Decision and Control, CDC 2018. Vol. 2018-December. Institute of Electrical and Electronics Engineers Inc. 2019. p. 4091-4096. 8618654 https://doi.org/10.1109/CDC.2018.8618654

Author

Troeng, Olof ; Falt, Mattias. / A Seemingly Polynomial-Time Algorithm for Optimal Curve Fitting by Segmented Straight Lines. 2018 IEEE Conference on Decision and Control, CDC 2018. Vol. 2018-December Institute of Electrical and Electronics Engineers Inc., 2019. pp. 4091-4096

RIS

TY - GEN

T1 - A Seemingly Polynomial-Time Algorithm for Optimal Curve Fitting by Segmented Straight Lines

AU - Troeng, Olof

AU - Falt, Mattias

PY - 2019/1/21

Y1 - 2019/1/21

N2 - We consider least-squares approximation of a function of one variable by a continuous, piecewise-linear approximand that has a small number of breakpoints. This problem was notably considered by Bellman who proposed an approximate algorithm based on dynamic programming. Many suboptimal approaches have been suggested, but so far, the only exact methods resort to mixed integer programming with superpolynomial complexity growth. In this paper, we present an exact and efficient algorithm based on dynamic programming with a hybrid value function. Empirical evidence suggest that the algorithm has a polynomial time complexity.

AB - We consider least-squares approximation of a function of one variable by a continuous, piecewise-linear approximand that has a small number of breakpoints. This problem was notably considered by Bellman who proposed an approximate algorithm based on dynamic programming. Many suboptimal approaches have been suggested, but so far, the only exact methods resort to mixed integer programming with superpolynomial complexity growth. In this paper, we present an exact and efficient algorithm based on dynamic programming with a hybrid value function. Empirical evidence suggest that the algorithm has a polynomial time complexity.

U2 - 10.1109/CDC.2018.8618654

DO - 10.1109/CDC.2018.8618654

M3 - Paper in conference proceeding

VL - 2018-December

SP - 4091

EP - 4096

BT - 2018 IEEE Conference on Decision and Control, CDC 2018

PB - Institute of Electrical and Electronics Engineers Inc.

ER -