Standard

Quadratic Euclidean 1-Mean and 1-Median 2-Clustering Problem with constraints on the size of the clusters : Complexity and approximability. / Kel'manov, Alexander Vasil evich; Pyatkin, Artem Valer evich; Khandeev, Vladimir Il ich.

In: Trudy Instituta Matematiki i Mekhaniki UrO RAN, Vol. 25, No. 4, 01.01.2019, p. 69-78.

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

Harvard

Kel'manov, AVE, Pyatkin, AVE & Khandeev, VII 2019, 'Quadratic Euclidean 1-Mean and 1-Median 2-Clustering Problem with constraints on the size of the clusters: Complexity and approximability', Trudy Instituta Matematiki i Mekhaniki UrO RAN, vol. 25, no. 4, pp. 69-78. https://doi.org/10.21538/0134-4889-2019-25-4-69-78

APA

Kel'manov, A. V. E., Pyatkin, A. V. E., & Khandeev, V. I. I. (2019). Quadratic Euclidean 1-Mean and 1-Median 2-Clustering Problem with constraints on the size of the clusters: Complexity and approximability. Trudy Instituta Matematiki i Mekhaniki UrO RAN, 25(4), 69-78. https://doi.org/10.21538/0134-4889-2019-25-4-69-78

Vancouver

Kel'manov AVE, Pyatkin AVE, Khandeev VII. Quadratic Euclidean 1-Mean and 1-Median 2-Clustering Problem with constraints on the size of the clusters: Complexity and approximability. Trudy Instituta Matematiki i Mekhaniki UrO RAN. 2019 Jan 1;25(4):69-78. doi: 10.21538/0134-4889-2019-25-4-69-78

Author

Kel'manov, Alexander Vasil evich ; Pyatkin, Artem Valer evich ; Khandeev, Vladimir Il ich. / Quadratic Euclidean 1-Mean and 1-Median 2-Clustering Problem with constraints on the size of the clusters : Complexity and approximability. In: Trudy Instituta Matematiki i Mekhaniki UrO RAN. 2019 ; Vol. 25, No. 4. pp. 69-78.

BibTeX

@article{961089da173c472e8cb997d65c9f662c,
title = "Quadratic Euclidean 1-Mean and 1-Median 2-Clustering Problem with constraints on the size of the clusters: Complexity and approximability",
abstract = "We consider the problem of partitioning a set of N points in d-dimensional Euclidean space into two clusters minimizing the sum of the squared distances between each element and the center of the cluster to which it belongs. The center of the first cluster is its centroid (the geometric center). The center of the second cluster should be chosen among the points of the input set. We analyze the variant of the problem with given sizes (cardinalities) of the clusters; the sum of the sizes equals the cardinality of the input set. We prove that the problem is strongly NP-hard and there is no fully polynomial-time approximation scheme for its solution.",
keywords = "2-partition, Approximation-preserving reduction, Center, Centroid, Clustering, Euclidean space, Median, Nonexistence of FPTAS, Quadratic variation, Strong NP-hardness, Euclidean space, clustering, 2-partition, quadratic variation, center, centroid, median, strong NP-hardness, nonexistence of FPTAS, approximation-preserving reduction",
author = "Kel'manov, {Alexander Vasil evich} and Pyatkin, {Artem Valer evich} and Khandeev, {Vladimir Il ich}",
note = "Кельманов А.В., Пяткин А.В., Хандеев В.И. Квадратичная евклидова задача 2-кластеризации 1-Mean и 1-Median с ограничением на размеры кластеров: сложность и аппроксимируемость // Тр. Ин-та математики и механики УрО РАН. - 2019. - Т. 25. - № 4. - С. 69-78",
year = "2019",
month = jan,
day = "1",
doi = "10.21538/0134-4889-2019-25-4-69-78",
language = "English",
volume = "25",
pages = "69--78",
journal = "Trudy Instituta Matematiki i Mekhaniki UrO RAN",
issn = "0134-4889",
publisher = "KRASOVSKII INST MATHEMATICS & MECHANICS URAL BRANCH RUSSIAN ACAD SCIENCES",
number = "4",

}

RIS

TY - JOUR

T1 - Quadratic Euclidean 1-Mean and 1-Median 2-Clustering Problem with constraints on the size of the clusters

T2 - Complexity and approximability

AU - Kel'manov, Alexander Vasil evich

AU - Pyatkin, Artem Valer evich

AU - Khandeev, Vladimir Il ich

N1 - Кельманов А.В., Пяткин А.В., Хандеев В.И. Квадратичная евклидова задача 2-кластеризации 1-Mean и 1-Median с ограничением на размеры кластеров: сложность и аппроксимируемость // Тр. Ин-та математики и механики УрО РАН. - 2019. - Т. 25. - № 4. - С. 69-78

PY - 2019/1/1

Y1 - 2019/1/1

N2 - We consider the problem of partitioning a set of N points in d-dimensional Euclidean space into two clusters minimizing the sum of the squared distances between each element and the center of the cluster to which it belongs. The center of the first cluster is its centroid (the geometric center). The center of the second cluster should be chosen among the points of the input set. We analyze the variant of the problem with given sizes (cardinalities) of the clusters; the sum of the sizes equals the cardinality of the input set. We prove that the problem is strongly NP-hard and there is no fully polynomial-time approximation scheme for its solution.

AB - We consider the problem of partitioning a set of N points in d-dimensional Euclidean space into two clusters minimizing the sum of the squared distances between each element and the center of the cluster to which it belongs. The center of the first cluster is its centroid (the geometric center). The center of the second cluster should be chosen among the points of the input set. We analyze the variant of the problem with given sizes (cardinalities) of the clusters; the sum of the sizes equals the cardinality of the input set. We prove that the problem is strongly NP-hard and there is no fully polynomial-time approximation scheme for its solution.

KW - 2-partition

KW - Approximation-preserving reduction

KW - Center

KW - Centroid

KW - Clustering

KW - Euclidean space

KW - Median

KW - Nonexistence of FPTAS

KW - Quadratic variation

KW - Strong NP-hardness

KW - Euclidean space

KW - clustering

KW - 2-partition

KW - quadratic variation

KW - center

KW - centroid

KW - median

KW - strong NP-hardness

KW - nonexistence of FPTAS

KW - approximation-preserving reduction

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

UR - https://www.elibrary.ru/item.asp?id=41455522

U2 - 10.21538/0134-4889-2019-25-4-69-78

DO - 10.21538/0134-4889-2019-25-4-69-78

M3 - Article

AN - SCOPUS:85078544596

VL - 25

SP - 69

EP - 78

JO - Trudy Instituta Matematiki i Mekhaniki UrO RAN

JF - Trudy Instituta Matematiki i Mekhaniki UrO RAN

SN - 0134-4889

IS - 4

ER -

ID: 23287203