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

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

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



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






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


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

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

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

А. В. Кельманов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
  • Дискретный анализ и исследование операций
    Просмотров:
    Эта страница:93
    Полный текст:10
    Литература:22
    Первая стр.:2

     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2019