Standard

NP-Hardness of 1-Mean and 1-Medoid 2-Clustering Problem with Arbitrary Clusters Sizes. / Pyatkin, Artem V.

Mathematical Optimization Theory and Operations Research: Recent Trends - 20th International Conference, MOTOR 2021, Revised Selected Papers. ed. / Alexander Strekalovsky; Yury Kochetov; Tatiana Gruzdeva; Andrei Orlov. Springer Science and Business Media Deutschland GmbH, 2021. p. 248-256 (Communications in Computer and Information Science; Vol. 1476 CCIS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Research › peer-review

Harvard

Pyatkin, AV 2021, NP-Hardness of 1-Mean and 1-Medoid 2-Clustering Problem with Arbitrary Clusters Sizes. in A Strekalovsky, Y Kochetov, T Gruzdeva & A Orlov (eds), Mathematical Optimization Theory and Operations Research: Recent Trends - 20th International Conference, MOTOR 2021, Revised Selected Papers. Communications in Computer and Information Science, vol. 1476 CCIS, Springer Science and Business Media Deutschland GmbH, pp. 248-256, 20th International Conference on Mathematical Optimization Theory and Operations Research , MOTOR 2021, Virtual, Online, 05.07.2021. https://doi.org/10.1007/978-3-030-86433-0_17

APA

Pyatkin, A. V. (2021). NP-Hardness of 1-Mean and 1-Medoid 2-Clustering Problem with Arbitrary Clusters Sizes. In A. Strekalovsky, Y. Kochetov, T. Gruzdeva, & A. Orlov (Eds.), Mathematical Optimization Theory and Operations Research: Recent Trends - 20th International Conference, MOTOR 2021, Revised Selected Papers (pp. 248-256). (Communications in Computer and Information Science; Vol. 1476 CCIS). Springer Science and Business Media Deutschland GmbH. https://doi.org/10.1007/978-3-030-86433-0_17

Vancouver

Pyatkin AV. NP-Hardness of 1-Mean and 1-Medoid 2-Clustering Problem with Arbitrary Clusters Sizes. In Strekalovsky A, Kochetov Y, Gruzdeva T, Orlov A, editors, Mathematical Optimization Theory and Operations Research: Recent Trends - 20th International Conference, MOTOR 2021, Revised Selected Papers. Springer Science and Business Media Deutschland GmbH. 2021. p. 248-256. (Communications in Computer and Information Science). doi: 10.1007/978-3-030-86433-0_17

Author

Pyatkin, Artem V. / NP-Hardness of 1-Mean and 1-Medoid 2-Clustering Problem with Arbitrary Clusters Sizes. Mathematical Optimization Theory and Operations Research: Recent Trends - 20th International Conference, MOTOR 2021, Revised Selected Papers. editor / Alexander Strekalovsky ; Yury Kochetov ; Tatiana Gruzdeva ; Andrei Orlov. Springer Science and Business Media Deutschland GmbH, 2021. pp. 248-256 (Communications in Computer and Information Science).

BibTeX

@inproceedings{c8c90d517fc04f3f82b016dd3af8bbe8,
title = "NP-Hardness of 1-Mean and 1-Medoid 2-Clustering Problem with Arbitrary Clusters Sizes",
abstract = "We consider the following 2-clustering problem. Given n points in Euclidean space, partition it into two subsets (clusters) so that the sum of squared distances between the elements of the clusters and their centers would be minimum. The center of the first cluster coincides with its centroid (mean) while the center of the second cluster should be chosen from the set of the initial points (medoid). It is known that this problem is NP-hard if the cardinalities of the clusters are given as a part of the input. In this paper we prove that the peoblem remains NP-hard in the case of arbitrary clusters sizes.",
keywords = "2-clustering, Euclidean space, Mean, Medoid, Strong NP-hardness",
author = "Pyatkin, {Artem V.}",
note = "Publisher Copyright: {\textcopyright} 2021, Springer Nature Switzerland AG.; 20th International Conference on Mathematical Optimization Theory and Operations Research , MOTOR 2021 ; Conference date: 05-07-2021 Through 10-07-2021",
year = "2021",
doi = "10.1007/978-3-030-86433-0_17",
language = "English",
isbn = "9783030864323",
series = "Communications in Computer and Information Science",
publisher = "Springer Science and Business Media Deutschland GmbH",
pages = "248--256",
editor = "Alexander Strekalovsky and Yury Kochetov and Tatiana Gruzdeva and Andrei Orlov",
booktitle = "Mathematical Optimization Theory and Operations Research",
address = "Germany",

}

RIS

TY - GEN

T1 - NP-Hardness of 1-Mean and 1-Medoid 2-Clustering Problem with Arbitrary Clusters Sizes

AU - Pyatkin, Artem V.

N1 - Publisher Copyright: © 2021, Springer Nature Switzerland AG.

PY - 2021

Y1 - 2021

N2 - We consider the following 2-clustering problem. Given n points in Euclidean space, partition it into two subsets (clusters) so that the sum of squared distances between the elements of the clusters and their centers would be minimum. The center of the first cluster coincides with its centroid (mean) while the center of the second cluster should be chosen from the set of the initial points (medoid). It is known that this problem is NP-hard if the cardinalities of the clusters are given as a part of the input. In this paper we prove that the peoblem remains NP-hard in the case of arbitrary clusters sizes.

AB - We consider the following 2-clustering problem. Given n points in Euclidean space, partition it into two subsets (clusters) so that the sum of squared distances between the elements of the clusters and their centers would be minimum. The center of the first cluster coincides with its centroid (mean) while the center of the second cluster should be chosen from the set of the initial points (medoid). It is known that this problem is NP-hard if the cardinalities of the clusters are given as a part of the input. In this paper we prove that the peoblem remains NP-hard in the case of arbitrary clusters sizes.

KW - 2-clustering

KW - Euclidean space

KW - Mean

KW - Medoid

KW - Strong NP-hardness

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

U2 - 10.1007/978-3-030-86433-0_17

DO - 10.1007/978-3-030-86433-0_17

M3 - Conference contribution

AN - SCOPUS:85115847034

SN - 9783030864323

T3 - Communications in Computer and Information Science

SP - 248

EP - 256

BT - Mathematical Optimization Theory and Operations Research

A2 - Strekalovsky, Alexander

A2 - Kochetov, Yury

A2 - Gruzdeva, Tatiana

A2 - Orlov, Andrei

PB - Springer Science and Business Media Deutschland GmbH

T2 - 20th International Conference on Mathematical Optimization Theory and Operations Research , MOTOR 2021

Y2 - 5 July 2021 through 10 July 2021

ER -

ID: 34339712