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
APA
CBE
MLA
Vancouver
Author
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
AN - SCOPUS:85062175829
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.
T2 - 57th IEEE Conference on Decision and Control, CDC 2018
Y2 - 17 December 2018 through 19 December 2018
ER -