Аннотация:
Рассматривается NP-трудная в сильном смысле задача разбиения конечной последовательности точек евклидова пространства на два кластера (подпоследовательности), имеющих заданные мощности, по критерию минимума суммы по обоим кластерам внутрикластерных сумм квадратов расстояний от элементов кластеров до их центров. Предполагается, что центр одного из искомых кластеров неизвестен и определяется как среднее значение по всем элементам, образующим этот кластер, а центр второго задан в начале координат. При этом разбиение подчинено условию: разность между номерами последующего и предыдущего элементов последовательности, входящих в первый кластер, ограничена сверху и снизу заданными константами. Обоснована полностью полиномиальная приближённая схема для случая задачи, в котором размерность пространства фиксирована. Библиогр. 27.
Образец цитирования:
А. В. Кельманов, С. А. Хамидуллин, В. И. Хандеев, “Полностью полиномиальная аппроксимационная схема для одной задачи двухкластерного разбиения последовательности”, Дискретн. анализ и исслед. опер., 23:2 (2016), 21–40; J. Appl. Industr. Math., 10:2 (2016), 209–219
\RBibitem{KelKhaKha16}
\by А.~В.~Кельманов, С.~А.~Хамидуллин, В.~И.~Хандеев
\paper Полностью полиномиальная аппроксимационная схема для одной задачи двухкластерного разбиения последовательности
\jour Дискретн. анализ и исслед. опер.
\yr 2016
\vol 23
\issue 2
\pages 21--40
\mathnet{http://mi.mathnet.ru/da843}
\crossref{https://doi.org/10.17377/daio.2016.23.511}
\mathscinet{http://mathscinet.ams.org/mathscinet-getitem?mr=3557592}
\elib{https://elibrary.ru/item.asp?id=26129765}
\transl
\jour J. Appl. Industr. Math.
\yr 2016
\vol 10
\issue 2
\pages 209--219
\crossref{https://doi.org/10.1134/S199047891602006X}
\scopus{https://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-84971334424}
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/da843
https://www.mathnet.ru/rus/da/v23/i2/p21
Эта публикация цитируется в следующих 9 статьяx:
Anna Panasenko, Communications in Computer and Information Science, 2239, Mathematical Optimization Theory and Operations Research: Recent Trends, 2024, 349
A. V. Kel'manov, V. I. Khandeev, A. V. Panasenko, “Exact Algorithms of Search For a Cluster of the Largest Size in Two Integer 2-Clustering Problems”, Numer. Anal. Appl., 12:2 (2019), 105–115
Alexander Kel'manov, Sergey Khamidullin, Vladimir Khandeev, Artem Pyatkin, Communications in Computer and Information Science, 974, Optimization and Applications, 2019, 131
А. В. Кельманов, С. А. Хамидуллин, В. И. Хандеев, “Рандомизированный алгоритм для задачи двухкластерного разбиения последовательности”, Ж. вычисл. матем. и матем. физ., 58:12 (2018), 2169–2178; A. V. Kel'manov, S. A. Khamidullin, V. I. Khandeev, “A randomized algorithm for a sequence 2-clustering problem”, Comput. Math. Math. Phys., 58:12 (2018), 2078–2085
A. Kel'manov, S. Khamidullin, V. Khandeev, “A randomized algorithm for 2-partition of a sequence”, Analysis of Images, Social Networks and Texts, AIST 2017, Lecture Notes in Computer Science, 10716, eds. W. van der Aalst, D. Ignatov, M. Khachay, S. Kuznetsov, V. Lempitsky, I. Lomazova, N. Loukachevitch, A. Napoli, A. Panchenko, P. Pardalos, A. Savchenko, S. Wasserman, Springer, 2018, 313–322
A. V. Kel'manov, S. A. Khamidullin, V. I. Khandeev, A. V. Pyatkin, “An Exact Algorithm of Searching for the Largest Cluster in an Integer-Valued Problem of 2-Partitioning a Sequence”, Pattern Recognit. Image Anal., 28:4 (2018), 703
A. Kel'manov, “Efficient approximation algorithms for some NP-hard problems of partitioning a set and a sequence”, 2017 International Multi-Conference on Engineering, Computer and Information Sciences (SIBIRCON), IEEE, 2017, 87–90
А. В. Кельманов, Л. В. Михайлова, С. А. Хамидуллин, В. И. Хандеев, “Приближенный алгоритм для задачи разбиения последовательности на кластеры с ограничениями на их мощность”, Тр. ИММ УрО РАН, 22, № 3, 2016, 144–152; A. V. Kel'manov, L. V. Mikhailova, S. A. Khamidullin, V. I. Khandeev, “An approximation algorithm for the problem of partitioning a sequence into clusters with constraints on their cardinalities”, Proc. Steklov Inst. Math. (Suppl.), 299, suppl. 1 (2017), 88–96
Alexander Kel'manov, Ludmila Mikhailova, Sergey Khamidullin, Vladimir Khandeev, Lecture Notes in Computer Science, 9869, Discrete Optimization and Operations Research, 2016, 171
Цитирование в формате AMSBIB
Обратная связь: