On the Complexity of Some Problems of Searching for a Family of Disjoint Clusters

A. V. Kel’manov; A. V. Pyatkin; V. I. Khandeev

doi:10.1134/S1064562419010162

On the Complexity of Some Problems of Searching for a Family of Disjoint Clusters

A. V. Kel’manov, A. V. Pyatkin, V. I. Khandeev

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

Аннотация

Abstract: Two consimilar problems of searching for a family of disjoint subsets (clusters) in a finite set of points of Euclidean space are considered. In these problems, the task is to maximize the minimum cluster size so that the value of each intercluster quadratic variation does not exceed a given fraction (constant) of the total quadratic variation of the points of the input set with respect to its centroid. Both problems are proved to be NP-hard even on a line.

Язык оригинала	английский
Страницы (с-по)	52-56
Число страниц	5
Журнал	Doklady Mathematics
Том	99
Номер выпуска	1
DOI	https://doi.org/10.1134/S1064562419010162
Состояние	Опубликовано - 1 янв. 2019

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

10.1134/S1064562419010162

Другие файлы и ссылки

Link to publication in Scopus

Fingerprint

Подробные сведения о темах исследования «On the Complexity of Some Problems of Searching for a Family of Disjoint Clusters». Вместе они формируют уникальный семантический отпечаток (fingerprint).

Цитировать

@article{b36cfe1459cf430b8948abca71f3192a,

title = "On the Complexity of Some Problems of Searching for a Family of Disjoint Clusters",

abstract = "Abstract: Two consimilar problems of searching for a family of disjoint subsets (clusters) in a finite set of points of Euclidean space are considered. In these problems, the task is to maximize the minimum cluster size so that the value of each intercluster quadratic variation does not exceed a given fraction (constant) of the total quadratic variation of the points of the input set with respect to its centroid. Both problems are proved to be NP-hard even on a line.",

keywords = "ALGORITHM, 2-CENTER",

author = "Kel{\textquoteright}manov, {A. V.} and Pyatkin, {A. V.} and Khandeev, {V. I.}",

year = "2019",

month = jan,

day = "1",

doi = "10.1134/S1064562419010162",

language = "English",

volume = "99",

pages = "52--56",

journal = "Doklady Mathematics",

issn = "1064-5624",

publisher = "Maik Nauka-Interperiodica Publishing",

number = "1",

}

On the Complexity of Some Problems of Searching for a Family of Disjoint Clusters. / Kel’manov, A. V.; Pyatkin, A. V.; Khandeev, V. I.

В: Doklady Mathematics, Том 99, № 1, 01.01.2019, стр. 52-56.

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

TY - JOUR

T1 - On the Complexity of Some Problems of Searching for a Family of Disjoint Clusters

AU - Kel’manov, A. V.

AU - Pyatkin, A. V.

AU - Khandeev, V. I.

PY - 2019/1/1

Y1 - 2019/1/1

N2 - Abstract: Two consimilar problems of searching for a family of disjoint subsets (clusters) in a finite set of points of Euclidean space are considered. In these problems, the task is to maximize the minimum cluster size so that the value of each intercluster quadratic variation does not exceed a given fraction (constant) of the total quadratic variation of the points of the input set with respect to its centroid. Both problems are proved to be NP-hard even on a line.

AB - Abstract: Two consimilar problems of searching for a family of disjoint subsets (clusters) in a finite set of points of Euclidean space are considered. In these problems, the task is to maximize the minimum cluster size so that the value of each intercluster quadratic variation does not exceed a given fraction (constant) of the total quadratic variation of the points of the input set with respect to its centroid. Both problems are proved to be NP-hard even on a line.

KW - ALGORITHM

KW - 2-CENTER

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

U2 - 10.1134/S1064562419010162

DO - 10.1134/S1064562419010162

M3 - Article

AN - SCOPUS:85065864468

VL - 99

SP - 52

EP - 56

JO - Doklady Mathematics

JF - Doklady Mathematics

SN - 1064-5624

IS - 1

ER -