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

Forskningsoutput: Kapitel i bok/rapport/Conference proceedingKonferenspaper i 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.

Detaljer

Författare
Enheter & grupper
Forskningsområden

Ämnesklassifikation (UKÄ) – OBLIGATORISK

  • Reglerteknik
Originalspråkengelska
Titel på värdpublikation2018 IEEE Conference on Decision and Control, CDC 2018
FörlagInstitute of Electrical and Electronics Engineers Inc.
Sidor4091-4096
Antal sidor6
Volym2018-December
ISBN (elektroniskt)9781538613955
StatusPublished - 2019 jan 21
PublikationskategoriForskning
Peer review utfördJa
Evenemang57th IEEE Conference on Decision and Control, CDC 2018 - Miami, USA
Varaktighet: 2018 dec 172018 dec 19

Konferens

Konferens57th IEEE Conference on Decision and Control, CDC 2018
LandUSA
OrtMiami
Period2018/12/172018/12/19