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

Research output: Chapter in Book/Report/Conference proceedingPaper in conference proceeding

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.

Details

Authors
Organisations
Research areas and keywords

Subject classification (UKÄ) – MANDATORY

  • Control Engineering
Original languageEnglish
Title of host publication2018 IEEE Conference on Decision and Control, CDC 2018
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages4091-4096
Number of pages6
Volume2018-December
ISBN (Electronic)9781538613955
Publication statusPublished - 2019 Jan 21
Publication categoryResearch
Peer-reviewedYes
Event57th IEEE Conference on Decision and Control, CDC 2018 - Miami, United States
Duration: 2018 Dec 172018 Dec 19

Conference

Conference57th IEEE Conference on Decision and Control, CDC 2018
CountryUnited States
CityMiami
Period2018/12/172018/12/19