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

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

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


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




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

Доклады Российской академии наук. Математика, информатика, процессы управления, 2023, том 514, номер 1, страницы 89–97
DOI: https://doi.org/10.31857/S268695432360218X (Mi danma438) 		 
МАТЕМАТИКА

Приближенные алгоритмы с фиксированными оценками точности для серии асимметричных задач маршрутизации

Е. Д. Незнахинаab, Ю. Ю. Огородниковab, К. В. Рыженкоa, М. Ю. Хачайa

a Институт математики и механики им. Н. Н. Красовского Уральского отделения РАН, Екатеринбург, Россия
b Уральский федеральный университет им. Б.Н. Ельцина, Екатеринбург, Россия
Список литературы:
PDF
HTML
DOI: https://doi.org/10.31857/S268695432360218X
Аннотация: Обосновываются первые алгоритмы с константными оценками точности для серии асимметричных постановок задач маршрутизации: задачи о штейнеровском цикле, задачи коммивояжера с призами, задачи о покрытии графа ограниченным числом циклов и др. В большинстве своем предложенные алгоритмы опираются на оригинальные схемы сведения исследуемых постановок к вспомогательным постановкам асимметричной задачи коммивояжера и прорывные результаты О. Свенссона, Я. Тарнавски, Л. Вега и В. Трауб, Й. Вигена в области эффективной аппроксимируемости данной задачи. Алгоритм для задачи о покрытии графа ограниченным числом циклов опирается на технику, связанную с более глубокой модификацией подхода Свенссона–Трауб.
Ключевые слова: асимметричная задача коммивояжера, приближенные алгоритмы, константная оценка точности, задача о штейнеровском цикле минимального веса, задача маршрутизации транспорта, задача о покрытии графа ограниченным числом циклов.
Финансовая поддержка Номер гранта
Российский научный фонд 22-21-00672
Данное исследование поддержано Российским научным фондом, грант № 22-21-00672, https://rscf.ru/en/project/22-21-00672/.
Поступило: 19.09.2023
После доработки: 18.10.2023
Принято к публикации: 05.11.2023
Англоязычная версия:
Doklady Mathematics, 2023, Volume 108, Issue 3, Pages 499–505
DOI: https://doi.org/10.1134/S1064562423701454
Реферативные базы данных:
Тип публикации: Статья
УДК: 519.16 + 519.85
Образец цитирования: Е. Д. Незнахина, Ю. Ю. Огородников, К. В. Рыженко, М. Ю. Хачай, “Приближенные алгоритмы с фиксированными оценками точности для серии асимметричных задач маршрутизации”, Докл. РАН. Матем., информ., проц. упр., 514:1 (2023), 89–97; Dokl. Math., 108:3 (2023), 499–505
Цитирование в формате AMSBIB
\RBibitem{NezOgoRyz23}
\by Е.~Д.~Незнахина, Ю.~Ю.~Огородников, К.~В.~Рыженко, М.~Ю.~Хачай
\paper Приближенные алгоритмы с фиксированными оценками точности для серии асимметричных задач маршрутизации
\jour Докл. РАН. Матем., информ., проц. упр.
\yr 2023
\vol 514
\issue 1
\pages 89--97
\mathnet{http://mi.mathnet.ru/danma438}
\crossref{https://doi.org/10.31857/S268695432360218X}
\elib{https://elibrary.ru/item.asp?id=56718079}
\transl
\jour Dokl. Math.
\yr 2023
\vol 108
\issue 3
\pages 499--505
\crossref{https://doi.org/10.1134/S1064562423701454}
Образцы ссылок на эту страницу:
  • https://www.mathnet.ru/rus/danma438
  • https://www.mathnet.ru/rus/danma/v514/i1/p89
    • Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    		Доклады Российской академии наук. Математика, информатика, процессы управления Доклады Российской академии наук. Математика, информатика, процессы управления
    Статистика просмотров:
    Страница аннотации:54
    Список литературы:21
     
      Обратная связь:
    		  Пользовательское соглашение  Регистрация посетителей портала  Логотипы © Математический институт им. В. А. Стеклова РАН, 2024