### Abstract

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 language | English |
---|---|

Pages (from-to) | 573-576 |

Number of pages | 4 |

Journal | Pattern Recognition and Image Analysis |

Volume | 29 |

Issue number | 4 |

DOIs | |

Publication status | Published - 1 Oct 2019 |

### Keywords

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

## Cite this

Kel’manov, A. V., & Ruzankin, P. S. (2019). An Accelerated Exact Algorithm for the One-Dimensional M-Variance Problem.

*Pattern Recognition and Image Analysis*,*29*(4), 573-576. https://doi.org/10.1134/S1054661819040072