Standard

On the Complexity of SomeMax-Min Clustering Problems. / Kel'manov, A. V.; Pyatkin, A. V.; Khandeev, V. I.

In: Proceedings of the Steklov Institute of Mathematics, Vol. 309, No. SUPPL 1, 08.2020, p. S65-S73.

Research output: Contribution to journal › Article › peer-review

Harvard

Kel'manov, AV, Pyatkin, AV & Khandeev, VI 2020, 'On the Complexity of SomeMax-Min Clustering Problems', Proceedings of the Steklov Institute of Mathematics, vol. 309, no. SUPPL 1, pp. S65-S73. https://doi.org/10.1134/S0081543820040082

APA

Kel'manov, A. V., Pyatkin, A. V., & Khandeev, V. I. (2020). On the Complexity of SomeMax-Min Clustering Problems. Proceedings of the Steklov Institute of Mathematics, 309(SUPPL 1), S65-S73. https://doi.org/10.1134/S0081543820040082

Vancouver

Kel'manov AV, Pyatkin AV, Khandeev VI. On the Complexity of SomeMax-Min Clustering Problems. Proceedings of the Steklov Institute of Mathematics. 2020 Aug;309(SUPPL 1):S65-S73. doi: 10.1134/S0081543820040082

Author

Kel'manov, A. V. ; Pyatkin, A. V. ; Khandeev, V. I. / On the Complexity of SomeMax-Min Clustering Problems. In: Proceedings of the Steklov Institute of Mathematics. 2020 ; Vol. 309, No. SUPPL 1. pp. S65-S73.

BibTeX

@article{0c0bfc88ddf443cb8fb8b22b12c27026,
title = "On the Complexity of SomeMax-Min Clustering Problems",
abstract = "Two similar problems of searching for a family of disjoint subsets (clusters) in a finite set of points in Euclidean space are considered. In these problems, the size of the smallest cluster should be maximized so that in each cluster the intracluster quadratic variation of the points with respect to the center of the cluster would not exceed a given (constant) fraction of the total quadratic variation of the points of the input set with respect to its centroid. In the first problem, the centers of intracluster variations are arbitrary points of the space given at the input. In the second problem, the centers of the intracluster variation are unknown (to be found) but must lie in the input set. Both problems are proved to be NP-hard even on the real line both in the general case when the number of the clusters is a part of the input and in the parametric case when the number of the clusters is fixed.",
keywords = "Euclidean space, clustering, max-min problem, quadratic variation, NP-hardness, NP-HARDNESS, max–min problem",
author = "Kel'manov, {A. V.} and Pyatkin, {A. V.} and Khandeev, {V. I.}",
note = "Funding Information: This work was supported by the Russian Science Foundation (project no. 16-11-10041). Publisher Copyright: {\textcopyright} Pleiades Publishing, Ltd., 2020. c.",
year = "2020",
month = aug,
doi = "10.1134/S0081543820040082",
language = "English",
volume = "309",
pages = "S65--S73",
journal = "Proceedings of the Steklov Institute of Mathematics",
issn = "0081-5438",
publisher = "Maik Nauka Publishing / Springer SBM",
number = "SUPPL 1",

}

RIS

TY - JOUR

T1 - On the Complexity of SomeMax-Min Clustering Problems

AU - Kel'manov, A. V.

AU - Pyatkin, A. V.

AU - Khandeev, V. I.

N1 - Funding Information: This work was supported by the Russian Science Foundation (project no. 16-11-10041). Publisher Copyright: © Pleiades Publishing, Ltd., 2020. c.

PY - 2020/8

Y1 - 2020/8

N2 - Two similar problems of searching for a family of disjoint subsets (clusters) in a finite set of points in Euclidean space are considered. In these problems, the size of the smallest cluster should be maximized so that in each cluster the intracluster quadratic variation of the points with respect to the center of the cluster would not exceed a given (constant) fraction of the total quadratic variation of the points of the input set with respect to its centroid. In the first problem, the centers of intracluster variations are arbitrary points of the space given at the input. In the second problem, the centers of the intracluster variation are unknown (to be found) but must lie in the input set. Both problems are proved to be NP-hard even on the real line both in the general case when the number of the clusters is a part of the input and in the parametric case when the number of the clusters is fixed.

AB - Two similar problems of searching for a family of disjoint subsets (clusters) in a finite set of points in Euclidean space are considered. In these problems, the size of the smallest cluster should be maximized so that in each cluster the intracluster quadratic variation of the points with respect to the center of the cluster would not exceed a given (constant) fraction of the total quadratic variation of the points of the input set with respect to its centroid. In the first problem, the centers of intracluster variations are arbitrary points of the space given at the input. In the second problem, the centers of the intracluster variation are unknown (to be found) but must lie in the input set. Both problems are proved to be NP-hard even on the real line both in the general case when the number of the clusters is a part of the input and in the parametric case when the number of the clusters is fixed.

KW - Euclidean space

KW - clustering

KW - max-min problem

KW - quadratic variation

KW - NP-hardness

KW - NP-HARDNESS

KW - max–min problem

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

U2 - 10.1134/S0081543820040082

DO - 10.1134/S0081543820040082

M3 - Article

VL - 309

SP - S65-S73

JO - Proceedings of the Steklov Institute of Mathematics

JF - Proceedings of the Steklov Institute of Mathematics

SN - 0081-5438

IS - SUPPL 1

ER -

ID: 26085181