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

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

doi:10.1134/S1054661819040072

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

Результат исследования: Научные публикации в периодических изданиях › статья

Аннотация

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.

Язык оригинала	английский
Страницы (с-по)	573-576
Число страниц	4
Журнал	Pattern Recognition and Image Analysis
Том	29
Номер выпуска	4
DOI	https://doi.org/10.1134/S1054661819040072
Состояние	Опубликовано - 1 окт 2019

Доступ к документу

10.1134/S1054661819040072

Link to publication in Scopus

Цитировать

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

@article{e52b99e7a65948d3a03908eb22e3ba43,

title = "An Accelerated Exact Algorithm for the One-Dimensional M-Variance Problem",

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.",

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

author = "Kel{\textquoteright}manov, {A. V.} and Ruzankin, {P. S.}",

year = "2019",

month = oct,

day = "1",

doi = "10.1134/S1054661819040072",

language = "English",

volume = "29",

pages = "573--576",

journal = "Pattern Recognition and Image Analysis",

issn = "1054-6618",

publisher = "Maik Nauka Publishing / Springer SBM",

number = "4",

}

TY - JOUR

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

AU - Kel’manov, A. V.

AU - Ruzankin, P. S.

PY - 2019/10/1

Y1 - 2019/10/1

N2 - 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.

AB - 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.

KW - $NP$-hard problem

KW - accelerated exact algorithm

KW - Euclidean space

KW - one-dimensional case

KW - quadratic scattering

KW - subset search

UR - http://www.scopus.com/inward/record.url?scp=85077075713&partnerID=8YFLogxK

U2 - 10.1134/S1054661819040072

DO - 10.1134/S1054661819040072

M3 - Article

AN - SCOPUS:85077075713

VL - 29

SP - 573

EP - 576

JO - Pattern Recognition and Image Analysis

JF - Pattern Recognition and Image Analysis

SN - 1054-6618

IS - 4

ER -