A Seemingly Polynomial-Time Algorithm for Optimal Curve Fitting by Segmented Straight Lines
(2019) 57th IEEE Conference on Decision and Control, CDC 2018 2018-December. p.4091-4096- Abstract
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.
Please use this url to cite or link to this publication:
https://lup.lub.lu.se/record/650b5eeb-4c3a-4599-95a2-acb4410c0bfc
- author
- Troeng, Olof LU and Falt, Mattias LU
- organization
- publishing date
- 2019-01-21
- type
- Chapter in Book/Report/Conference proceeding
- publication status
- published
- subject
- host publication
- 2018 IEEE Conference on Decision and Control, CDC 2018
- volume
- 2018-December
- article number
- 8618654
- pages
- 6 pages
- publisher
- IEEE - Institute of Electrical and Electronics Engineers Inc.
- conference name
- 57th IEEE Conference on Decision and Control, CDC 2018
- conference location
- Miami, United States
- conference dates
- 2018-12-17 - 2018-12-19
- external identifiers
-
- scopus:85062175829
- ISBN
- 9781538613955
- DOI
- 10.1109/CDC.2018.8618654
- language
- English
- LU publication?
- yes
- id
- 650b5eeb-4c3a-4599-95a2-acb4410c0bfc
- date added to LUP
- 2019-03-11 13:00:28
- date last changed
- 2022-05-03 18:46:29
@inproceedings{650b5eeb-4c3a-4599-95a2-acb4410c0bfc, abstract = {{<p>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.</p>}}, author = {{Troeng, Olof and Falt, Mattias}}, booktitle = {{2018 IEEE Conference on Decision and Control, CDC 2018}}, isbn = {{9781538613955}}, language = {{eng}}, month = {{01}}, pages = {{4091--4096}}, publisher = {{IEEE - Institute of Electrical and Electronics Engineers Inc.}}, title = {{A Seemingly Polynomial-Time Algorithm for Optimal Curve Fitting by Segmented Straight Lines}}, url = {{http://dx.doi.org/10.1109/CDC.2018.8618654}}, doi = {{10.1109/CDC.2018.8618654}}, volume = {{2018-December}}, year = {{2019}}, }