An Accelerated Exact Algorithm for the One-Dimensional M-Variance Problem

Resumo

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.