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

Alexander Vasil evich Kel'manov; Artem Valer evich Pyatkin; Vladimir Il ich Khandeev

doi:10.21538/0134-4889-2019-25-4-69-78

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

Переведенное название: Квадратичная евклидова задача 2-кластеризации 1-Mean и 1-Median с ограничением на размеры кластеров: сложность и аппроксимируемость

Alexander Vasil evich Kel'manov, Artem Valer evich Pyatkin, Vladimir Il ich Khandeev

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

Аннотация

В работе рассматривается задача кластеризации N-элементного множества точек в d-мерном евклидовом пространстве на два кластера. В этой задаче требуется найти 2-разбиение, минимизирующее сумму (по обоим кластерам) внутрикластерных квадратичных разбросов точек относительно искомых центров. Центр одного кластера определяется как центроид (геометрический центр), а центр другого кластера является искомой точкой во входном множестве. Анализируется вариант задачи, в котором размеры (т. е. мощности) кластеров заданы, а их суммарный размер совпадает с размером входного множества. Доказано, что задача NP-трудна в сильном смысле. Установлено, что для нее не существует полностью полиномиальной аппроксимационной схемы, если P≠ NP

Переведенное название	Квадратичная евклидова задача 2-кластеризации 1-Mean и 1-Median с ограничением на размеры кластеров: сложность и аппроксимируемость
Язык оригинала	английский
Страницы (с-по)	69-78
Число страниц	10
Журнал	Trudy Instituta Matematiki i Mekhaniki UrO RAN
Том	25
Номер выпуска	4
DOI	https://doi.org/10.21538/0134-4889-2019-25-4-69-78
Состояние	Опубликовано - 1 янв 2019

Ключевые слова

2-partition
Approximation-preserving reduction
Center
Centroid
Clustering
Euclidean space
Median
Nonexistence of FPTAS
Quadratic variation
Strong NP-hardness

ГРНТИ

27 МАТЕМАТИКА

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

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

Fingerprint Подробные сведения о темах исследования «Квадратичная евклидова задача 2-кластеризации 1-Mean и 1-Median с ограничением на размеры кластеров: сложность и аппроксимируемость». Вместе они формируют уникальный семантический отпечаток (fingerprint).

Цитировать

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

}

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.

В: Trudy Instituta Matematiki i Mekhaniki UrO RAN, Том 25, № 4, 01.01.2019, стр. 69-78.

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

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 -