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

A. V. Kel’manov, P. S. Ruzankin

Research output: Contribution to journalArticle


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 (Formula presented.)(N logN) is proposed.

Original languageEnglish
Pages (from-to)573-576
Number of pages4
JournalPattern Recognition and Image Analysis
Issue number4
Publication statusPublished - 1 Oct 2019


  • $NP$-hard problem
  • accelerated exact algorithm
  • Euclidean space
  • one-dimensional case
  • quadratic scattering
  • subset search

Cite this