Fitting a graph to one-dimensional data

Cited 0 time in webofscience Cited 0 time in scopus
  • Hit : 76
  • Download : 0
Given n data points in R-d , an appropriate edge-weighted graph connecting the data points finds application in solving clustering, classification, and regression problems. The graph proposed by Daitch, Kelner and Spielman (ICML 2009) can be computed by quadratic programming and hence in polynomial time. While a more efficient algorithm would be preferable, replacing quadratic programming is challenging even for the special case of points in one dimension. We develop a dynamic programming algorithm for this case that runs in O(n(2)) time under the Real-RAM model, where arithmetic on real numbers takes constant time. (C) 2021 Elsevier B.V. All rights reserved.
Publisher
ELSEVIER
Issue Date
2021-05
Language
English
Article Type
Article
Citation

THEORETICAL COMPUTER SCIENCE, v.867, pp.40 - 49

ISSN
0304-3975
DOI
10.1016/j.tcs.2021.03.020
URI
http://hdl.handle.net/10203/285308
Appears in Collection
CS-Journal Papers(저널논문)
Files in This Item
There are no files associated with this item.

qr_code

  • mendeley

    citeulike


rss_1.0 rss_2.0 atom_1.0