Том 1, номер 2, 1994 г., Стр. 8-17
УДК 519.8
Э. Х. Гимади, Н. И. Глебов, А. И. Сердюков
Алгоритм для приближенного решения задачи коммивояжера и его вероятностный анализ
Аннотация:
Рассмотрен один полиномиальный алгоритм для приближенного решения задачи коммивояжера, использующий в качестве процедуры алгоритм решения задачи о назначениях. Для достаточно широкого класса вероятностных распределений на множестве входов задачи проведен вероятностный анализ и установлена асимптотическая точность алгоритма.
Библиогр. 10.
Гимади Э. X. 1
Глебов Н. И. 1
Сердюков А. И. 1
1. Институт математики им. С. Л. Соболева СО РАН,
пр. Акад. Коптюга, 4, 630090 Новосибирск, Россия
Статья поступила 15 марта 1994 г.
