Том 8, серия 2, номер 1, 2001 г., Стр. 22-39
УДК 519.8
Э. Х. Гимади, А. И. Сердюков
О некоторых результатах для задачи коммивояжёра на максимум
Аннотация:
Доказана теорема об изометричном вложении с сохранением. Приводится краткий обзор исследований приближенных алгоритмов с оценками для задачи коммивояжера на максимум (MAX TSP). Основное внимание обращается на специальные классы задачи MAX TSP: симметрическая, полуметрическая, метрическая (симметрическая и полуметрическая), полиэдральная и евклидова. Для задачи со случайными входами представлены результаты вероятностного анализа двух алгоритмов, использующих эвристики «Иди в удаленный город» и «Склейка контуров».
Ил. 3, библиогр. 30.
Гимади Э. X. 1
Сердюков А. И. 1
1. Институт математики им. С. Л. Соболева СО РАН,
пр. Акад. Коптюга, 4, 630090 Новосибирск, Россия
е-mail: gimadi@math.nsc.ru
Статья поступила 8 января 2001 г.
