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

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

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



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






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


Дискретн. анализ и исслед. опер., 2016, том 23, номер 2, страницы 21–40 (Mi da843)  

Эта публикация цитируется в 4 научных статьях (всего в 4 статьях)

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

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

a Новосибирский государственный университет, ул. Пирогова, 2, 630090 Новосибирск, Россия
b Институт математики им. С. Л. Соболева, пр. Коптюга, 4, 630090 Новосибирск, Россия

Аннотация: Рассматривается NP-трудная в сильном смысле задача разбиения конечной последовательности точек евклидова пространства на два кластера (подпоследовательности), имеющих заданные мощности, по критерию минимума суммы по обоим кластерам внутрикластерных сумм квадратов расстояний от элементов кластеров до их центров. Предполагается, что центр одного из искомых кластеров неизвестен и определяется как среднее значение по всем элементам, образующим этот кластер, а центр второго задан в начале координат. При этом разбиение подчинено условию: разность между номерами последующего и предыдущего элементов последовательности, входящих в первый кластер, ограничена сверху и снизу заданными константами. Обоснована полностью полиномиальная приближённая схема для случая задачи, в котором размерность пространства фиксирована. Библиогр. 27.

Ключевые слова: разбиение, последовательность, евклидово пространство, минимум суммы квадратов расстояний, NP-трудность, FPTAS.

Финансовая поддержка Номер гранта
Российский фонд фундаментальных исследований 15-01-00462
16-07-00168
16-31-00186-мол-а
Исследование выполнено при финансовой поддержке Российского фонда фундаментальных исследований (проекты 15-01-00462, 16-07-00168 и 16-31-00186-мол-а).


DOI: https://doi.org/10.17377/daio.2016.23.511

Полный текст: PDF файл (299 kB)
Список литературы: PDF файл   HTML файл

Англоязычная версия:
Journal of Applied and Industrial Mathematics, 2016, 10:2, 209–219

Реферативные базы данных:

Тип публикации: Статья
УДК: 519.16+519.85
Статья поступила: 15.09.2015
Переработанный вариант: 12.01.2016

Образец цитирования: А. В. Кельманов, С. А. Хамидуллин, В. И. Хандеев, “Полностью полиномиальная аппроксимационная схема для одной задачи двухкластерного разбиения последовательности”, Дискретн. анализ и исслед. опер., 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://www.ams.org/mathscinet-getitem?mr=3557592}
\elib{http://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{http://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-84971334424}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/da843
  • http://mi.mathnet.ru/rus/da/v23/i2/p21

    ОТПРАВИТЬ: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles

    Эта публикация цитируется в следующих статьяx:
    1. А. В. Кельманов, Л. В. Михайлова, С. А. Хамидуллин, В. И. Хандеев, “Приближенный алгоритм для задачи разбиения последовательности на кластеры с ограничениями на их мощность”, Тр. ИММ УрО РАН, 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
    2. 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
    3. А. В. Кельманов, С. А. Хамидуллин, В. И. Хандеев, “Рандомизированный алгоритм для задачи двухкластерного разбиения последовательности”, Ж. вычисл. матем. и матем. физ., 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
    4. 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
  • Дискретный анализ и исследование операций
    Просмотров:
    Эта страница:151
    Полный текст:18
    Литература:34
    Первая стр.:2
     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2019