Email this article An Accelerated Exact Algorithm for the One-Dimensional M-Variance Problem
- Authors: Kel’manov A.V.1,2, Ruzankin P.S.1,2
-
Affiliations:
- Sobolev Institute of Mathematics,
- Novosibirsk State University
- Issue: Vol 29, No 4 (2019)
- Pages: 573-576
- Section: Mathematical Theory of Pattern Recognition
- URL: https://bakhtiniada.ru/1054-6618/article/view/195705
- DOI: https://doi.org/10.1134/S1054661819040072
- ID: 195705
Cite item
Open Access
Access granted
Subscription Access
Abstract
The known quadratic \(NP\)-hard (in the strong sense) \(M\)-variance problem is considered. It arises in the following typical problem of data analysis: in a set of \(N\) objects determined by their characteristics (features), find a subset of \(M\) elements close to each other. For the one-dimensional case, an accelerated exact algorithm with complexity \(\mathcal{O}(N{\kern 1pt} \log{\kern 1pt} N)\) is proposed.
About the authors
A. V. Kel’manov
Sobolev Institute of Mathematics,; Novosibirsk State University
Author for correspondence.
Email: kelm@math.nsc.ru
Russian Federation, Novosibirsk, 630090; Novosibirsk, 630090
P. S. Ruzankin
Sobolev Institute of Mathematics,; Novosibirsk State University
Author for correspondence.
Email: ruzankin@math.nsc.ru
Russian Federation, Novosibirsk, 630090; Novosibirsk, 630090
Supplementary files
