Кельманов, А. В. Рандомизированный алгоритм для одной задачи двухкластерного разбиения множества векторов [Текст] / А. В. Кельманов, В. И. Хандеев // Журнал вычислительной математики и математической физики. - 2015. - Т. 55, № 2. - С. 335-344. - Библиогр.: c. 343-344 . - ISSN 0044-4669
Рубрики: Математика Вычислительная математика Кл.слова (ненормированные): NP-трудность -- асимптотические точности -- двухкластерное разбиение множества -- задачи кластерного анализа -- квадраты евклидовых расстояний -- множества векторов -- рандомизированные алгоритмы Аннотация: Обоснован рандомизированный алгоритм для NP-трудной в сильном смысле задачи разбиения конечного множества векторов евклидова пространства на два кластера заданных размеров по критерию минимума суммы квадратов расстояний от элементов кластеров до их центров. Предполагается, что центр одного из кластеров является оптимизируемой величиной и определяется как среднее значение по всем векторам, образующим этот кластер. Центр другого кластера фиксирован в начале координат. Предложенный алгоритм при заданных относительной ошибке и вероятности несрабатывания для установленного значения параметра находит приближенное решение задачи за линейное от размерности пространства и размера входа задачи время. Найдены условия, при которых алгоритм асимптотически точен и позволяет находить решение за время, линейное от размерности пространства и квадратичное от размера входа задачи. Доп.точки доступа: Хандеев, В. И. Нет сведений об экземплярах (Источник в БД не найден) |