Асимптотически точный алгоритм для задачи нескольких коммивояжёров на случайных входных данных с дискретным распределением | Sciact - Система учета научной деятельности ИМ СО РАН

Асимптотически точный алгоритм для задачи нескольких коммивояжёров на случайных входных данных с дискретным распределением Научная публикация

Журнал

Дискретный анализ и исследование операций
ISSN: 1560-7542

Вых. Данные

Год: 2017, Том: 24, Номер: 3, Страницы: 5-19 Страниц : 15 DOI: 10.17377/daio.2017.24.551

Авторы

Гимади Эдуард Хайрутдинович ^1,2 , Цидулко Оксана Юрьевна ^1,2

Организации

1	Институт математики им. С.Л. Соболева СО РАН
2	Новосибирский государственный университет

Рассматривается задача m коммивояжёров (m-Peripatetic Salesman Problem) на случайных входных данных c дискретным распределением. Для её решения предлагается приближённый по- линомиальный алгоритм, который при определённых ограничениях на входные данные с вероятностью, стремящейся к 1 с ростом раз- мерности задачи, даёт точное решение задачи m-PSP как с одинако- выми, так и с различными весовыми функциями маршрутов комми- вояжёров.

Гимади Э.Х. , Цидулко О.Ю.
Асимптотически точный алгоритм для задачи нескольких коммивояжёров на случайных входных данных с дискретным распределением
Дискретный анализ и исследование операций. 2017. Т.24. №3. С.5-19. DOI: 10.17377/daio.2017.24.551

Gimadi E.K. , Tsidulko O.Y.
An asymptotically optimal algorithm for the m-Peripatetic Salesman Problem on random inputs with discrete distribution
Journal of Applied and Industrial Mathematics. 2017. V.11. N3. P.354-361. DOI: 10.1134/s1990478917030061 Scopus OpenAlex

Нет идентификаторов

Пока нет цитирований