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

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

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

Статья «NP-ТРУДНОСТЬ НЕКОТОРЫХ ЕВКЛИДОВЫХ ЗАДАЧ РАЗБИЕНИЯ КОНЕЧНОГО МНОЖЕСТВА ТОЧЕК1), "Журнал вычислительной математики и математической физики"»

Авторы:
  • Кельманов А.В.1
  • Пяткин А.В.2
стр. 852-856
Платно
1 Институт математики им. С.Л. Соболева СО РАН, 2 (630090 Новосибирск, пр. Ак. Коптюга, 4, Ин-т матем. СО РАН, 630090 Новосибирск, ул. Пирогова, 2, НГУ)
Ключевые слова:
  • Разбиение
  • евклидово пространство
  • норма суммы
  • NP-трудность
Аннотация:
Рассматриваются задачи разбиения конечного множества точек евклидова пространства на кластеры по критерию минимума суммы по всем кластерам: деленных на мощность квадратов норм внутрикластерных сумм элементов; квадратов норм внутрикластерных сумм элементов; норм внутрикластерных сумм элементов. Доказано, что все задачи NP-трудны в сильном смысле, если число кластеров является частью входа, и NP-трудны в обычном смысле, если число кластеров не является частью входа (фиксировано). Установлено, что все задачи NP-трудны даже в одномерном случае (на прямой). Библ. 6.

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

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

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