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

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

Journal

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

Output data

Year: 2017, Volume: 24, Number: 3, Pages: 5-19 Pages count : 15 DOI: 10.17377/daio.2017.24.551

Authors

Gimadi Éduard Khairutdinovich ^1,2 , Tsidulko Oxana Yurievna ^1,2

Affiliations

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

No identifiers

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