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

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

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



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






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


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

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

Вероятностный анализ алгоритма решения трёхиндексной $m$-слойной планарной задачи о назначениях на одноциклических подстановках

Э. Х. Гимадиab, Ю. В. Глазковb, О. Ю. Цидулкоb

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

Аннотация: Рассматривается трёхиндексная планарная $m$-слойная задача о назначениях на одноциклических подстановках, являющаяся в общем случае задачей $m$ коммивояжёров с различными весовыми функциями их маршрутов. Задача NP-трудна при $m\ge1$. Представлен приближённый полиномиальный алгоритм решения задачи при $1<m<n/4$. Алгоритм имеет временну́ю сложность $O(mn^2)$. Получены оценки качества его работы в случае, когда входные данные (элементы $(m\times n\times n)$-матрицы) являются независимыми случайными величинами с общей функцией равномерного распределения на отрезке $[a_n,b_n]$, где $0<a_n<b_n$. Получены условия асимптотической точности алгоритма, верные также в случае функции распределения мажорирующего типа. Ил. 1, библиогр. 26.

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

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

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

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

Тип публикации: Статья
УДК: 519.8
Статья поступила: 19.12.2012
Переработанный вариант: 29.03.2013

Образец цитирования: Э. Х. Гимади, Ю. В. Глазков, О. Ю. Цидулко, “Вероятностный анализ алгоритма решения трёхиндексной $m$-слойной планарной задачи о назначениях на одноциклических подстановках”, Дискретн. анализ и исслед. опер., 21:1 (2014), 15–29; J. Appl. Industr. Math., 8:2 (2014), 208–217

Цитирование в формате AMSBIB
\RBibitem{GimGlaTsi14}
\by Э.~Х.~Гимади, Ю.~В.~Глазков, О.~Ю.~Цидулко
\paper Вероятностный анализ алгоритма решения тр\"ехиндексной $m$-слойной планарной задачи о~назначениях на одноциклических подстановках
\jour Дискретн. анализ и исслед. опер.
\yr 2014
\vol 21
\issue 1
\pages 15--29
\mathnet{http://mi.mathnet.ru/da757}
\mathscinet{http://www.ams.org/mathscinet-getitem?mr=3288378}
\transl
\jour J. Appl. Industr. Math.
\yr 2014
\vol 8
\issue 2
\pages 208--217
\crossref{https://doi.org/10.1134/S1990478914020070}
\isi{http://gateway.isiknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&DestLinkType=FullRecord&DestApp=ALL_WOS&KeyUT=000377429900002}
\scopus{http://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-84902148101}


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

    ОТПРАВИТЬ: 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. Э. Х. Гимади, А. М. Истомин, И. А. Рыков, О. Ю. Цидулко, “Вероятностный анализ приближенного алгоритма для решения задачи о нескольких коммивояжерах на случайных входных данных, неограниченных сверху”, Тр. ИММ УрО РАН, 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
    2. Gimadi E.Kh., “Efficient Algorithms With Performance Guarantees For Some Problems of Finding Several Discrete Disjoint Subgraphs in Complete Weighted Graph”, Appl. Math. Comput., 255 (2015), 84–91  crossref  mathscinet  zmath  isi  elib  scopus
    3. Э. Х. Гимади, О. Ю. Цидулко, “Асимптотически точный алгоритм для задачи нескольких коммивояжёров на случайных входных данных с дискретным распределением”, Дискретн. анализ и исслед. опер., 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
    4. 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. 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, 304–312  crossref  mathscinet  isi  scopus
    5. M. Khachay, K. Neznakhina, “Polynomial time solvable subclass of the Generalized Traveling Salesman Problem on Grid Clusters”, 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, 346–355  crossref  isi  scopus
  • Дискретный анализ и исследование операций
    Просмотров:
    Эта страница:334
    Полный текст:73
    Литература:31
    Первая стр.:9
     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2020