Skip to main content

Lund University Publications

LUND UNIVERSITY LIBRARIES

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

Troeng, Olof LU and Falt, Mattias LU (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:
author
and
organization
publishing date
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}},
}