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

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

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



Журн. СФУ. Сер. Матем. и физ.:
Год:
Том:
Выпуск:
Страница:
Найти






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


Журн. СФУ. Сер. Матем. и физ., 2019, том 12, выпуск 5, страницы 621–627 (Mi jsfu798)  

On accuracy of approximation for the resource constrained shortest path problem

[О точности аппроксимации для задачи о ресурсоограниченном кратчайшем пути]

Aleksandr A. Soldatenko

Institute of Mathematics and Computer Science, Siberian Federal University, Svobodny, 79, Krasnoyarsk, 660041, Russia

Аннотация: Рассматривается NP-трудная задача поиска ресурсоограниченного кратчайшего пути, известная под названием Resource Constrained Shortest Path (RCSP). Задача RCSP является расширением задачи о кратчайшем пути в ориентированном графе $G = (V, E)$, когда для каждой дуги $e \in E$ кроме основной весовой функции $w(e)$ дополнительно задаются функции $r_i(e), i = 1, …, k$, численно отражающие потребности в ресурсах, которые необходимы для передвижения по этой дуге. Предлагается полиномиальный $\epsilon$-приближенный алгоритм RevTree, использующий специальную маркировку вершин. Основное преимущество алгоритма RevTree по сравнению с существующими алгоритмами: он быстро находит допустимое решение задачи за $\mathcal{O}(\mathopen|V\mathclose|^2)$ время, отклоняясь от оптимального решения на величину, не превышающую $\epsilon$. В работе приведены доказательства оценок сложности и точности алгоритма RevTree.

DOI: https://doi.org/10.17516/1997-1397-2019-12-5-621-627

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

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

Тип публикации: Статья
УДК: 519.2
Получена: 14.02.2019
Исправленный вариант: 20.05.2019
Принята: 20.08.2019
Язык публикации: английский

Образец цитирования: Aleksandr A. Soldatenko, “On accuracy of approximation for the resource constrained shortest path problem”, Журн. СФУ. Сер. Матем. и физ., 12:5 (2019), 621–627

Цитирование в формате AMSBIB
\RBibitem{Sol19}
\by Aleksandr~A.~Soldatenko
\paper On accuracy of approximation for the resource constrained shortest path problem
\jour Журн. СФУ. Сер. Матем. и физ.
\yr 2019
\vol 12
\issue 5
\pages 621--627
\mathnet{http://mi.mathnet.ru/jsfu798}
\crossref{https://doi.org/10.17516/1997-1397-2019-12-5-621-627}
\isi{http://gateway.isiknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&DestLinkType=FullRecord&DestApp=ALL_WOS&KeyUT=000501589200011}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/jsfu798
  • http://mi.mathnet.ru/rus/jsfu/v12/i5/p621

    ОТПРАВИТЬ: 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
  • Журнал Сибирского федерального университета. Серия "Математика и физика"
    Просмотров:
    Эта страница:46
    Полный текст:5
    Литература:4
     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2020