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

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

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


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




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

Автоматика и телемеханика, 2017, выпуск 1, страницы 80–90 (Mi at14658)  
Эта публикация цитируется в 7 научных статьях (всего в 7 статьях)

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

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

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

a Институт математики им. С. Л. Соболева СО РАН, Новосибирск
b Новосибирский государственный университет
PDF полного текста (644 kB) Список цитирования (7)
Список литературы:
PDF
HTML
Аннотация: Рассматривается NP-трудная в сильном смысле задача разбиения конечной последовательности векторов евклидова пространства на два кластера заданных размеров по критерию минимума суммы по обоим кластерам сумм квадратов расстояний от элементов кластеров до их центров. Центр первого кластера является оптимизируемой величиной и определяется как среднее значение по всем векторам, образующим этот кластер. Центр второго кластера фиксирован в начале координат. При этом разбиение подчинено условию: разность между номерами последующего и предыдущего векторов, включаемых в первый кластер, ограничена сверху и снизу заданными константами. Предложен точный псевдополиномиальный алгоритм для случая задачи, в котором размерность пространства фиксирована, а компоненты входных векторов целочисленны.
Ключевые слова: разбиение, векторная последовательность, евклидово пространство, минимум суммы квадратов расстояний, NP-трудность, точный псевдополиномиальный алгоритм.
Финансовая поддержка Номер гранта
Российский фонд фундаментальных исследований 15-01-00462
16-07-00168
16-31-00186-мол-а
Работа выполнена при финансовой поддержке Российского фонда фундаментальных исследований (проекты №№ 15-01-00462, 16-07-00168, 16-31-00186-мол-а).
Статья представлена к публикации членом редколлегии: А. А. Лазарев

Поступила в редакцию: 12.01.2015
Англоязычная версия:
Automation and Remote Control, 2017, Volume 78, Issue 1, Pages 67–74
DOI: https://doi.org/10.1134/S0005117917010052
Реферативные базы данных:
Тип публикации: Статья
Образец цитирования: А. В. Кельманов, С. А. Хамидуллин, В. И. Хандеев, “Точный псевдополиномиальный алгоритм для одной задачи разбиения последовательности”, Автомат. и телемех., 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{https://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{https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=Publons&SrcAuth=Publons_CEL&DestLinkType=FullRecord&DestApp=WOS_CPL&KeyUT=000394180700005}
\scopus{https://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-85011807605}
Образцы ссылок на эту страницу:
  • https://www.mathnet.ru/rus/at14658
  • https://www.mathnet.ru/rus/at/y2017/i1/p80
    • Эта публикация цитируется в следующих 7 статьяx:
    1. Anna Panasenko, Communications in Computer and Information Science, 2239, Mathematical Optimization Theory and Operations Research: Recent Trends, 2024, 349  crossref
    2. A. Kel'manov, S. Khamidullin, A. Panasenko, “2-approximation polynomial-time algorithm for a cardinality-weighted 2-partitioning problem of a sequence”, Numerical Computations: Theory and Algorithms, Pt II, Lecture Notes in Computer Science, 11974, eds. Y. Sergeyev, D. Kvasov, Springer, 2020, 386–393  crossref  mathscinet  zmath  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. 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
    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. 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. 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  scopus
    Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    		Автоматика и телемеханика
    Статистика просмотров:
    Страница аннотации:393
    PDF полного текста:51
    Список литературы:53
    Первая страница:33
     
      Обратная связь:
    		  Пользовательское соглашение  Регистрация посетителей портала  Логотипы © Математический институт им. В. А. Стеклова РАН, 2025