Аннотация
В работе рассматривается задача кластеризации N-элементного множества точек в d-мерном евклидовом пространстве на два кластера. В этой задаче требуется найти 2-разбиение, минимизирующее сумму (по обоим кластерам) внутрикластерных квадратичных разбросов точек относительно искомых центров. Центр одного кластера определяется как центроид (геометрический центр), а центр другого кластера является искомой точкой во входном множестве. Анализируется вариант задачи, в котором размеры (т. е. мощности) кластеров заданы, а их суммарный размер совпадает с размером входного множества. Доказано, что задача NP-трудна в сильном смысле. Установлено, что для нее не существует полностью полиномиальной аппроксимационной схемы, если P≠ NP
Переведенное название | Квадратичная евклидова задача 2-кластеризации 1-Mean и 1-Median с ограничением на размеры кластеров: сложность и аппроксимируемость |
---|---|
Язык оригинала | английский |
Страницы (с-по) | 69-78 |
Число страниц | 10 |
Журнал | Trudy Instituta Matematiki i Mekhaniki UrO RAN |
Том | 25 |
Номер выпуска | 4 |
DOI | |
Состояние | Опубликовано - 1 янв 2019 |
Ключевые слова
- 2-partition
- Approximation-preserving reduction
- Center
- Centroid
- Clustering
- Euclidean space
- Median
- Nonexistence of FPTAS
- Quadratic variation
- Strong NP-hardness
ГРНТИ
- 27 МАТЕМАТИКА