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
СостояниеОпубликовано - 1 янв 2019

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

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

ГРНТИ

  • 27 МАТЕМАТИКА

Fingerprint

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

Цитировать