Аннотация:
Рассматриваются задачи разбиения конечного множества точек евклидова пространства на кластеры по критерию минимума суммы по всем кластерам: деленных на мощность квадратов норм внутрикластерных сумм элементов; квадратов норм внутрикластерных сумм элементов; норм внутрикластерных сумм элементов. Доказано, что все задачи NP-трудны в сильном смысле, если число кластеров является частью входа, и NP-трудны в обычном смысле, если число кластеров не является частью входа (фиксировано). Установлено, что все задачи NP-трудны даже в одномерном случае (на прямой). Библ. 6.
Образец цитирования:
А. В. Кельманов, А. В. Пяткин, “NP-трудность некоторых евклидовых задач разбиения конечного множества точек”, Ж. вычисл. матем. и матем. физ., 58:5 (2018), 852–856; Comput. Math. Math. Phys., 58:5 (2018), 822–826
\RBibitem{KelPya18}
\by А.~В.~Кельманов, А.~В.~Пяткин
\paper NP-трудность некоторых евклидовых задач разбиения конечного множества точек
\jour Ж. вычисл. матем. и матем. физ.
\yr 2018
\vol 58
\issue 5
\pages 852--856
\mathnet{http://mi.mathnet.ru/zvmmf10742}
\crossref{https://doi.org/10.7868/S0044466918050149}
\elib{https://elibrary.ru/item.asp?id=34914381}
\transl
\jour Comput. Math. Math. Phys.
\yr 2018
\vol 58
\issue 5
\pages 822--826
\crossref{https://doi.org/10.1134/S0965542518050123}
\isi{https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=Publons&SrcAuth=Publons_CEL&DestLinkType=FullRecord&DestApp=WOS_CPL&KeyUT=000435404100015}
\scopus{https://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-85048616703}
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/zvmmf10742
https://www.mathnet.ru/rus/zvmmf/v58/i5/p852
Эта публикация цитируется в следующих 5 статьяx:
Meigen Huang, Bi Gong, Xin Zhou, Tao Wang, Yanfeng Wang, “HIC: A high‐reliable in‐band control network for perception layer of software‐defined IoT”, Trans Emerging Tel Tech, 34:8 (2023)
A. L. Reznik, A. A. Soloviev, “Solving Fundamental and Applied Problems of Digital Image Processing at the Institute of Automation and Electrometry and Other Scientific Schools of the Siberian Branch of the Russian Academy of Sciences”, Pattern Recognit. Image Anal., 33:4 (2023), 1260
И. А. Борисова, “Вычислительная сложность задачи выбора типичных представителей в 2-разбиении конечного множества точек метрического пространства”, Дискретн. анализ и исслед. опер., 27:2 (2020), 5–16; I. A. Borisova, “Computational complexity of the problem of choosing typical representatives in a 2-clustering of a finite set of points in a metric space”, J. Appl. Industr. Math., 14:2 (2020), 242–248
O. M. Razumnikova, Y. A. Mezentsev, “Relationship of creativity, emotional and general intelligence intelligence with academic achievement of students”, Vopr. Psikhologii, 2020, no. 2, 119+
А. В. Кельманов, А. В. Пяткин, В. И. Хандеев, “О сложности некоторых максиминных задач кластеризации”, Тр. ИММ УрО РАН, 24, № 4, 2018, 189–198; A. V. Kel'manov, A. V. Pyatkin, V. I. Khandeev, “On the Complexity of Some Max–Min Clustering Problems”, Proc. Steklov Inst. Math. (Suppl.), 309, suppl. 1 (2020), S65–S73
Цитирование в формате AMSBIB
Обратная связь: