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

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

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



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






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


Дискретн. анализ и исслед. опер., 2014, том 21, номер 1, страницы 53–66 (Mi da760)  

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

Приближённый полиномиальный алгоритм для одной задачи разбиения последовательности

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

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

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

Ключевые слова: последовательность евклидовых векторов, кластеризация, минимум суммы квадратов расстояний, NP-трудность, полиномиальный $2$-приближённый алгоритм.

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

Англоязычная версия:
Journal of Applied and Industrial Mathematics, 2014, 8:2, 236–244

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

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

Образец цитирования: А. В. Кельманов, С. А. Хамидуллин, “Приближённый полиномиальный алгоритм для одной задачи разбиения последовательности”, Дискретн. анализ и исслед. опер., 21:1 (2014), 53–66; J. Appl. Industr. Math., 8:2 (2014), 236–244

Цитирование в формате AMSBIB
\RBibitem{KelKha14}
\by А.~В.~Кельманов, С.~А.~Хамидуллин
\paper Приближ\"енный полиномиальный алгоритм для одной задачи разбиения последовательности
\jour Дискретн. анализ и исслед. опер.
\yr 2014
\vol 21
\issue 1
\pages 53--66
\mathnet{http://mi.mathnet.ru/da760}
\mathscinet{http://www.ams.org/mathscinet-getitem?mr=3288381}
\transl
\jour J. Appl. Industr. Math.
\yr 2014
\vol 8
\issue 2
\pages 236--244
\crossref{https://doi.org/10.1134/S1990478914020100}
\scopus{http://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-84902178105}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/da760
  • http://mi.mathnet.ru/rus/da/v21/i1/p53

    ОТПРАВИТЬ: 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. А. В. Кельманов, С. А. Хамидуллин, В. И. Хандеев, “Полностью полиномиальная аппроксимационная схема для одной задачи двухкластерного разбиения последовательности”, Дискретн. анализ и исслед. опер., 23:2 (2016), 21–40  mathnet  crossref  mathscinet  elib; A. V. Kel'manov, S. A. Khamidullin, V. I. Khandeev, “Fully polynomial-time approximation scheme for a sequence $2$-clustering problem”, J. Appl. Industr. Math., 10:2 (2016), 209–219  crossref
    2. А. В. Кельманов, Л. В. Михайлова, С. А. Хамидуллин, В. И. Хандеев, “Приближенный алгоритм для задачи разбиения последовательности на кластеры с ограничениями на их мощность”, Тр. ИММ УрО РАН, 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
    3. А. В. Кельманов, С. А. Хамидуллин, В. И. Хандеев, “Точный псевдополиномиальный алгоритм для одной задачи разбиения последовательности”, Автомат. и телемех., 2017, № 1, 80–90  mathnet  elib; A. V. Kel'manov, S. A. Khamidullin, V. I. Khandeev, “Exact pseudopolynomial algorithm for one sequence partitioning problem”, Autom. Remote Control, 78:1 (2017), 67–74  crossref  isi
    4. 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
    5. А. В. Кельманов, С. А. Хамидуллин, В. И. Хандеев, “Рандомизированный алгоритм для задачи двухкластерного разбиения последовательности”, Ж. вычисл. матем. и матем. физ., 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
    6. 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
  • Дискретный анализ и исследование операций
    Просмотров:
    Эта страница:247
    Полный текст:52
    Литература:53
    Первая стр.:20
     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2019