|
Эта публикация цитируется в 16 научных статьях (всего в 16 статьях)
Полностью полиномиальная аппроксимационная схема для специального случая одной квадратичной евклидовой задачи 2-кластеризации
А. В. Кельмановab, В. И. Хандеевab a 630090 Новосибирск, пр-т Акад. Коптюга, 4, Ин-т математики СО РАН
b 630090 Новосибирск, ул. Пирогова, 2, Новосибирск. гос. ун-т
Аннотация:
Рассматривается $\mathrm{NP}$-трудная в сильном смысле задача разбиения конечного множества точек евклидова пространства на два кластера заданных размеров по критерию минимума суммы по обоим кластерам сумм квадратов внутрикластерных расстояний от элементов кластеров до их центров. Предполагается, что центр одного из искомых кластеров задан в желаемой (произвольной) точке пространства (без ограничения общности — в начале координат), а центр другого неизвестен и определяется как среднее значение по всем элементам, образующим этот кластер. Установлено, что для этой задачи не существует полностью полиномиальной приближенной схемы, если $\mathrm{P\ne NP}$, и такая схема обоснована для случая, когда размерность пространства фиксирована. Библ. 29.
Ключевые слова:
кластерный анализ, разбиение, евклидово пространство, минимум суммы квадратов расстояний, $\mathrm{NP}$-трудность, фиксированная размерность пространства, FPTAS.
Поступила в редакцию: 02.03.2015
Образец цитирования:
А. В. Кельманов, В. И. Хандеев, “Полностью полиномиальная аппроксимационная схема для специального случая одной квадратичной евклидовой задачи 2-кластеризации”, Ж. вычисл. матем. и матем. физ., 56:2 (2016), 332–340; Comput. Math. Math. Phys., 56:2 (2016), 334–341
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/zvmmf10348 https://www.mathnet.ru/rus/zvmmf/v56/i2/p332
|
|