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

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

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



Тр. ИММ УрО РАН:
Год:
Том:
Выпуск:
Страница:
Найти






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


Тр. ИММ УрО РАН, 2010, том 16, номер 3, страницы 12–24 (Mi timm572)  

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

Об асимптотической точности эффективного алгоритма решения задачи $m$-PSP на максимум в многомерном eвклидовом пространстве

А. Е. Бабурин, Э. Х. Гимадиa

a Ин-т математики им. С. Л. Соболева СО РАН

Аннотация: Представлен эффективный алгоритм $\mathcal A$ с гарантированной оценкой точности для решения задачи отыскания нескольких реберно-непересекающихся гамильтоновых циклов (маршрутов коммивояжера) максимального веса в полном взвешенном неориентированном графе в многомерном евклидовом пространстве $\mathbb R^k$. Трудоемкость алгоритма $O(n^3)$. Приводится обоснование числа маршрутов коммивояжера, при котором алгоритм является асимптотически точным.

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

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

Англоязычная версия:
Proceedings of the Steklov Institute of Mathematics (Supplementary issues), 2011, 272, suppl. 1, S1–S13

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

Тип публикации: Статья
УДК: 519.8
Поступила в редакцию: 31.03.2010

Образец цитирования: А. Е. Бабурин, Э. Х. Гимади, “Об асимптотической точности эффективного алгоритма решения задачи $m$-PSP на максимум в многомерном eвклидовом пространстве”, Тр. ИММ УрО РАН, 16, № 3, 2010, 12–24; Proc. Steklov Inst. Math. (Suppl.), 272, suppl. 1 (2011), S1–S13

Цитирование в формате AMSBIB
\RBibitem{BabGim10}
\by А.~Е.~Бабурин, Э.~Х.~Гимади
\paper Об асимптотической точности эффективного алгоритма решения задачи $m$-PSP на максимум в~многомерном eвклидовом пространстве
\serial Тр. ИММ УрО РАН
\yr 2010
\vol 16
\issue 3
\pages 12--24
\mathnet{http://mi.mathnet.ru/timm572}
\elib{http://elibrary.ru/item.asp?id=15173460}
\transl
\jour Proc. Steklov Inst. Math. (Suppl.)
\yr 2011
\vol 272
\issue , suppl. 1
\pages S1--S13
\crossref{https://doi.org/10.1134/S0081543811020015}
\isi{http://gateway.isiknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&DestLinkType=FullRecord&DestApp=ALL_WOS&KeyUT=000289527400001}
\scopus{http://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-79954620627}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/timm572
  • http://mi.mathnet.ru/rus/timm/v16/i3/p12

    ОТПРАВИТЬ: 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. E. Duchenne, G. Laporte, F. Semet, “The Undirected M-Capacitated Peripatetic Salesman Problem”, Eur. J. Oper. Res., 223:3 (2012), 637–643  crossref  mathscinet  zmath  isi  elib  scopus
    2. Э. Х. Гимади, Ю. В. Глазков, О. Ю. Цидулко, “Вероятностный анализ алгоритма решения трёхиндексной $m$-слойной планарной задачи о назначениях на одноциклических подстановках”, Дискретн. анализ и исслед. опер., 21:1 (2014), 15–29  mathnet  mathscinet; E. Kh. Gimadi, Yu. V. Glazkov, O. Yu. Tsidulko, “The probabilistic analysis of an algorithm for solving the $m$-planar $3$-dimensional assignment problem on one-cycle permutations”, J. Appl. Industr. Math., 8:2 (2014), 208–217  crossref  isi
    3. Э. Х. Гимади, А. М. Истомин, И. А. Рыков, О. Ю. Цидулко, “Вероятностный анализ приближенного алгоритма для решения задачи о нескольких коммивояжерах на случайных входных данных, неограниченных сверху”, Тр. ИММ УрО РАН, 20, № 2, 2014, 88–98  mathnet  mathscinet  elib; E. Kh. Gimadi, A. M. Istomin, I. A. Rykov, O. Yu. Tsidulko, “Probabilistic analysis of an approximation algorithm for the $m$-peripatetic salesman problem on random instances unbounded from above”, Proc. Steklov Inst. Math. (Suppl.), 289, suppl. 1 (2015), 77–87  crossref  isi
    4. Э. Х. Гимади, А. В. Кельманов, А. В. Пяткин, М. Ю. Хачай, “Эффективные алгоритмы с оценками точности для некоторых задач поиска нескольких клик в полном неориентированном взвешенном графе”, Тр. ИММ УрО РАН, 20, № 2, 2014, 99–112  mathnet  mathscinet  elib; E. Kh. Gimadi, A. V. Kel'manov, A. V. Pyatkin, M. Yu. Khachai, “Efficient algorithms with performance estimates for some problems of finding several cliques in a complete undirected weighted graph”, Proc. Steklov Inst. Math. (Suppl.), 289, suppl. 1 (2015), 88–101  crossref  isi
    5. V. V. Shenmaier, “Asymptotically Optimal Algorithms for Geometric Max TSP and Max M-PSP”, Discrete Appl. Math., 163:2, SI (2014), 214–219  crossref  mathscinet  zmath  isi  elib  scopus
    6. М. Ю. Хачай, Е. Д. Незнахина, “Полиномиальная приближенная схема для евклидовой задачи о цикловом покрытии графа”, Тр. ИММ УрО РАН, 20, № 4, 2014, 297–311  mathnet  mathscinet  elib; M. Yu. Khachai, E. D. Neznakhina, “Polynomial-time approximation scheme for a Euclidean problem on a cycle covering of a graph”, Proc. Steklov Inst. Math. (Suppl.), 289, suppl. 1 (2015), 111–125  crossref  isi
    7. М. Ю. Хачай, Е. Д. Незнахина, “Аппроксимируемость задачи о минимальном по весу цикловом покрытии графа”, Докл. РАН, 461:6 (2015), 644–649  crossref  elib; Khachai M.Yu., Neznakhina E.D., “Approximability of the Problem About a Minimum-Weight Cycle Cover of a Graph”, Dokl. Math., 91:2 (2015), 240–245  crossref  mathscinet  zmath  isi  elib  scopus
    8. Э. Х. Гимади, О. Ю. Цидулко, “Асимптотически точный алгоритм для задачи нескольких коммивояжёров на случайных входных данных с дискретным распределением”, Дискретн. анализ и исслед. опер., 24:3 (2017), 5–19  mathnet  crossref  elib; E. Kh. Gimadi, O. Yu. Tsidulko, “An asymptotically optimal algorithm for the $m$-peripatetic salesman problem on random inputs with discrete distribution”, J. Appl. Industr. Math., 11:3 (2017), 354–361  crossref
    9. E. Kh. Gimadi, O. Yu. Tsidulko, “Approximation Algorithms For the Maximum M-Peripatetic Salesman Problem”, Analysis of Images, Social Networks and Texts, AIST 2017, Lecture Notes in Computer Science, 10716, eds. Van Der Aalst W., Ignatov D., Khachay M., Kuznetsov S., Lempitsky V., Lomazova I., Loukachevitch N.,, Springer International Publishing Ag, 2018, 304–312  crossref  isi  scopus
    10. А. Н. Глебов, С. Г. Токтохоева, “Полиномиальный $3/5$-приближённый алгоритм для несимметричной задачи о трёх коммивояжёрах на максимум”, Дискретн. анализ и исслед. опер., 26:2 (2019), 30–59  mathnet  crossref
  • Труды Института математики и механики УрО РАН
    Просмотров:
    Эта страница:263
    Полный текст:63
    Литература:29

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