|
Эта публикация цитируется в 8 научных статьях (всего в 8 статьях)
Приближенный полиномиальный алгоритм для задачи взвешенной 2-кластеризации с ограничением на мощности кластеров
А. В. Кельмановab, А. В. Мотковаab a 630090 Новосибирск, пр-т Акад. Коптюга, 4, Ин-т матем. им. Соболева
b 630090 Новосибирск, ул. Пирогова, 2, Новосибирский гос. ун-т
Аннотация:
Рассматривается NP-трудная в сильном смысле задача двухкластерного разбиения конечного множества точек евклидова пространства. Критерием решения является минимум суммы по обоим кластерам взвешенных сумм квадратов внутрикластерных расстояний от элементов кластеров до их центров. Веса сумм равны мощностям искомых кластеров. Центр одного из кластеров задан на входе, а центр другого неизвестен и определяется как точка пространства, равная среднему значению элементов кластера. Анализируется вариант задачи, в котором мощности кластеров заданы на входе. Построен 2-приближенный полиномиальный алгоритм решения задачи. Библ. 25.
Ключевые слова:
евклидово пространство, взвешенная 2-кластеризация, NP-трудность, 2-приближенный полиномиальный алгоритм.
Поступила в редакцию: 18.06.2016 Исправленный вариант: 20.07.2017
Образец цитирования:
А. В. Кельманов, А. В. Моткова, “Приближенный полиномиальный алгоритм для задачи взвешенной 2-кластеризации с ограничением на мощности кластеров”, Ж. вычисл. матем. и матем. физ., 58:1 (2018), 136–142; Comput. Math. Math. Phys., 58:1 (2018), 130–136
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/zvmmf10665 https://www.mathnet.ru/rus/zvmmf/v58/i1/p136
|
Статистика просмотров: |
Страница аннотации: | 243 | Список литературы: | 38 |
|