|
Эта публикация цитируется в 1 научной статье (всего в 1 статье)
Рандомизированные алгоритмы для некоторых труднорешаемых задач кластеризации конечного множества точек евклидова пространства
А. В. Кельмановab, А. В. Панасенкоab, В. И. Хандеевab a 630090 Новосибирск, пр-т Акад. Коптюга, 4, Ин-т матем. им. С.Л. Соболева СО РАН, Россия
b 630090 Новосибирск, ул. Пирогова, 2, Новосибирский гос. ун-т, Россия
Аннотация:
Рассматриваются две NP-трудные в сильном смысле задачи кластеризации конечного множества точек евклидова пространства. Во входном множестве первой задачи требуется найти кластер (подмножество) заданной мощности, минимизирующий сумму квадратов расстояний между элементами этого кластера и его центроидом (геометрическим центром). Каждая точка вне этого кластера рассматривается как одноэлементный кластер. Во второй задаче требуется найти разбиение входного множества на два кластера, минимизирующее сумму по обоим кластерам взвешенных внутрикластерных сумм квадратов расстояний между элементами кластеров и их центрами. Центр одного из кластеров неизвестен и определяется как его центроид, а центр второго кластера задан в некоторой точке пространства (без ограничения общности этой точкой является начало координат). Весовыми множителями внутрикластерных сумм являются заданные мощности искомых кластеров. Для обеих задач предложены рандомизированные параметризованные алгоритмы. Для заданных верхних границ относительной ошибки и вероятности несрабатывания определено значение параметра, при котором алгоритмы находят приближенные решения задач за полиномиальное время. Это время линейно зависит как от размерности пространства, так и от мощности входного множества. Найдены условия, при которых оба алгоритма находят асимптотически точные решения и имеют трудоемкость, линейно зависящую от размерности пространства и квадратично — от мощности входного множества. Библ. 27.
Ключевые слова:
разбиение, последовательность, евклидово пространство, минимум суммы квадратов расстояний, NP-трудность, приближенный алгоритм.
Поступила в редакцию: 23.03.2018 Исправленный вариант: 11.01.2019 Принята в печать: 11.01.2019
Образец цитирования:
А. В. Кельманов, А. В. Панасенко, В. И. Хандеев, “Рандомизированные алгоритмы для некоторых труднорешаемых задач кластеризации конечного множества точек евклидова пространства”, Ж. вычисл. матем. и матем. физ., 59:5 (2019), 895–904; Comput. Math. Math. Phys., 59:5 (2019), 842–850
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/zvmmf10901 https://www.mathnet.ru/rus/zvmmf/v59/i5/p895
|
Статистика просмотров: |
Страница аннотации: | 115 | Список литературы: | 5 |
|