|
Эта публикация цитируется в 5 научных статьях (всего в 5 статьях)
NP-трудность некоторых евклидовых задач разбиения конечного множества точек
А. В. Кельмановab, А. В. Пяткинab a 630090 Новосибирск, пр-т акад. Коптюга, 4, Ин-т матем. РАН
b 630090 Новосибирск, ул. Пирогова, 2, Новосибирский гос. ун-т
Аннотация:
Рассматриваются задачи разбиения конечного множества точек евклидова пространства на кластеры по критерию минимума суммы по всем кластерам: деленных на мощность квадратов норм внутрикластерных сумм элементов; квадратов норм внутрикластерных сумм элементов; норм внутрикластерных сумм элементов. Доказано, что все задачи NP-трудны в сильном смысле, если число кластеров является частью входа, и NP-трудны в обычном смысле, если число кластеров не является частью входа (фиксировано). Установлено, что все задачи NP-трудны даже в одномерном случае (на прямой). Библ. 6.
Ключевые слова:
разбиение, евклидово пространство, норма суммы, NP-трудность.
Поступила в редакцию: 06.06.2016
Образец цитирования:
А. В. Кельманов, А. В. Пяткин, “NP-трудность некоторых евклидовых задач разбиения конечного множества точек”, Ж. вычисл. матем. и матем. физ., 58:5 (2018), 852–856; Comput. Math. Math. Phys., 58:5 (2018), 822–826
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/zvmmf10742 https://www.mathnet.ru/rus/zvmmf/v58/i5/p852
|
Статистика просмотров: |
Страница аннотации: | 217 | Список литературы: | 33 |
|