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

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

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



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






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


Автомат. и телемех., 2017, выпуск 1, страницы 80–90 (Mi at14658)  

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

Системный анализ и исследование операций

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

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

a Институт математики им. С. Л. Соболева СО РАН, Новосибирск
b Новосибирский государственный университет

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

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

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


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

Англоязычная версия:
Automation and Remote Control, 2017, 78:1, 67–74

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

Тип публикации: Статья
Статья представлена к публикации членом редколлегии: А. А. Лазарев

Поступила в редакцию: 12.01.2015

Образец цитирования: А. В. Кельманов, С. А. Хамидуллин, В. И. Хандеев, “Точный псевдополиномиальный алгоритм для одной задачи разбиения последовательности”, Автомат. и телемех., 2017, № 1, 80–90; Autom. Remote Control, 78:1 (2017), 67–74

Цитирование в формате AMSBIB
\RBibitem{KelKhaKha17}
\by А.~В.~Кельманов, С.~А.~Хамидуллин, В.~И.~Хандеев
\paper Точный псевдополиномиальный алгоритм для одной задачи разбиения последовательности
\jour Автомат. и телемех.
\yr 2017
\issue 1
\pages 80--90
\mathnet{http://mi.mathnet.ru/at14658}
\elib{http://elibrary.ru/item.asp?id=28317448}
\transl
\jour Autom. Remote Control
\yr 2017
\vol 78
\issue 1
\pages 67--74
\crossref{https://doi.org/10.1134/S0005117917010052}
\isi{http://gateway.isiknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&DestLinkType=FullRecord&DestApp=ALL_WOS&KeyUT=000394180700005}
\scopus{http://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-85011807605}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/at14658
  • http://mi.mathnet.ru/rus/at/y2017/i1/p80

    ОТПРАВИТЬ: 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. Kel'manov A., “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
    2. 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, Springer, 2018, 313–322  crossref  isi  scopus
    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
  • Автоматика и телемеханика
    Просмотров:
    Эта страница:192
    Литература:24
    Первая стр.:33
     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2019