Войти / Регистрация
Корзина

  • Ваша корзина пуста
Войти / Регистрация
Корзина

  • Ваша корзина пуста

Статья «ПРИБЛИЖЕННЫЙ ПОЛИНОМИАЛЬНЫЙ АЛГОРИТМ ДЛЯ ЗАДАЧИ ВЗВЕШЕННОЙ 2-КЛАСТЕРИЗАЦИИ С ОГРАНИЧЕНИЕМ НА МОЩНОСТИ КЛАСТЕРОВ^, "Журнал вычислительной математики и математической физики"»

Авторы:
  • Кельманов А.В.1
  • Моткова А. В.2
стр. 136-142
Платно
1 Институт математики им. С.Л. Соболева СО РАН, 2 Ин-т матем. им. Соболева; Новосибирский гос. ун-т
Ключевые слова:
  • евклидово пространство
  • взвешенная 2-кластеризация
  • NP-трудность
  • 2-приближенный полиномиальный алгоритм
Аннотация:
Рассматривается NP-трудная в сильном смысле задача двухкластерного разбиения конечного множества точек евклидова пространства. Критерием решения является минимум суммы по обоим кластерам взвешенных сумм квадратов внутрикластерных расстояний от элементов кластеров до их центров. Веса сумм равны мощностям искомых кластеров. Центр одного из кластеров задан на входе, а центр другого неизвестен и определяется как точка пространства, равная среднему значению элементов кластера. Анализируется вариант задачи, в котором мощности кластеров заданы на входе. Построен 2-приближенный полиномиальный алгоритм решения задачи. Библ. 25.

Архивные статьи (2015 год и ранее) доступны для ознакомления бесплатно, для скачивания их необходимо приобрести. Для просмотра материалов необходимо зарегистрироваться и авторизоваться на сайте.

Чтобы приобрести доступ к материалу для юридического лица, пожалуйста, свяжитесь с администрацией портала с помощью формы обратной связи либо по электронному адресу libnauka@naukaran.com.  

Действия с материалами доступны только авторизованным пользователям.