Loading [MathJax]/jax/output/SVG/config.js
Дискретный анализ и исследование операций
RUS  ENG    ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ПАКЕТ AMSBIB  
Общая информация
Последний выпуск
Архив
Импакт-фактор
Правила для авторов

Поиск публикаций
Поиск ссылок

RSS
Последний выпуск
Текущие выпуски
Архивные выпуски
Что такое RSS


Дискретн. анализ и исслед. опер.:
Год:
Том:
Выпуск:
Страница:
Найти




Персональный вход:
Логин:
Пароль:
Запомнить пароль
Войти
Забыли пароль?
Регистрация

Дискретный анализ и исследование операций, 2016, том 23, выпуск 2, страницы 21–40
DOI: https://doi.org/10.17377/daio.2016.23.511 (Mi da843) 		 
Эта публикация цитируется в 9 научных статьях (всего в 9 статьях)

Полностью полиномиальная аппроксимационная схема для одной задачи двухкластерного разбиения последовательности

А. В. Кельмановab, С. А. Хамидуллинb, В. И. Хандеевb

a Новосибирский государственный университет, ул. Пирогова, 2, 630090 Новосибирск, Россия
b Институт математики им. С. Л. Соболева, пр. Коптюга, 4, 630090 Новосибирск, Россия
PDF полного текста (299 kB) Список цитирования (9)
Список литературы:
PDF
HTML
DOI: https://doi.org/10.17377/daio.2016.23.511
Аннотация: Рассматривается NP-трудная в сильном смысле задача разбиения конечной последовательности точек евклидова пространства на два кластера (подпоследовательности), имеющих заданные мощности, по критерию минимума суммы по обоим кластерам внутрикластерных сумм квадратов расстояний от элементов кластеров до их центров. Предполагается, что центр одного из искомых кластеров неизвестен и определяется как среднее значение по всем элементам, образующим этот кластер, а центр второго задан в начале координат. При этом разбиение подчинено условию: разность между номерами последующего и предыдущего элементов последовательности, входящих в первый кластер, ограничена сверху и снизу заданными константами. Обоснована полностью полиномиальная приближённая схема для случая задачи, в котором размерность пространства фиксирована. Библиогр. 27.
Ключевые слова: разбиение, последовательность, евклидово пространство, минимум суммы квадратов расстояний, NP-трудность, FPTAS.
Финансовая поддержка Номер гранта
Российский фонд фундаментальных исследований 15-01-00462
16-07-00168
16-31-00186-мол-а
Исследование выполнено при финансовой поддержке Российского фонда фундаментальных исследований (проекты 15-01-00462, 16-07-00168 и 16-31-00186-мол-а).
Статья поступила: 15.09.2015
Переработанный вариант: 12.01.2016
Англоязычная версия:
Journal of Applied and Industrial Mathematics, 2016, Volume 10, Issue 2, Pages 209–219
DOI: https://doi.org/10.1134/S199047891602006X
Реферативные базы данных:
Тип публикации: Статья
УДК: 519.16+519.85
Образец цитирования: А. В. Кельманов, С. А. Хамидуллин, В. И. Хандеев, “Полностью полиномиальная аппроксимационная схема для одной задачи двухкластерного разбиения последовательности”, Дискретн. анализ и исслед. опер., 23:2 (2016), 21–40; J. Appl. Industr. Math., 10:2 (2016), 209–219
Цитирование в формате AMSBIB
\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:
    1. Anna Panasenko, Communications in Computer and Information Science, 2239, Mathematical Optimization Theory and Operations Research: Recent Trends, 2024, 349  crossref
    2. 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  mathnet  crossref  mathscinet  isi  scopus
    3. Alexander Kel'manov, Sergey Khamidullin, Vladimir Khandeev, Artem Pyatkin, Communications in Computer and Information Science, 974, Optimization and Applications, 2019, 131  crossref
    4. А. В. Кельманов, С. А. Хамидуллин, В. И. Хандеев, “Рандомизированный алгоритм для задачи двухкластерного разбиения последовательности”, Ж. вычисл. матем. и матем. физ., 58:12 (2018), 2169–2178  mathnet  crossref  elib; 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  crossref  isi
    5. 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  crossref  mathscinet  isi  scopus
    6. 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  crossref
    7. 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  crossref  isi
    8. А. В. Кельманов, Л. В. Михайлова, С. А. Хамидуллин, В. И. Хандеев, “Приближенный алгоритм для задачи разбиения последовательности на кластеры с ограничениями на их мощность”, Тр. ИММ УрО РАН, 22, № 3, 2016, 144–152  mathnet  crossref  mathscinet  elib; 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  crossref  isi
    9. Alexander Kel'manov, Ludmila Mikhailova, Sergey Khamidullin, Vladimir Khandeev, Lecture Notes in Computer Science, 9869, Discrete Optimization and Operations Research, 2016, 171  crossref
    Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    		Дискретный анализ и исследование операций
    Статистика просмотров:
    Страница аннотации:371
    PDF полного текста:70
    Список литературы:65
    Первая страница:2
     
      Обратная связь:
    math-net2025_03@mi-ras.ru     		 Пользовательское соглашение  Регистрация посетителей портала  Логотипы © Математический институт им. В. А. Стеклова РАН, 2025