О некоторых результатах для задачи коммивояжера на максимум

Доказана теорема об изометричном вложении с сохранением. Приводится краткий обзор исследований приближенных алгоритмов с оценками для задачи коммивояжера на максимум (MAX TSP). Основное внимание обращается на специальные классы задачи MAX TSP: симметрическая, полуметрическая, метрическая (симметрическая и полуметрическая), полиэдральная и евклидова. Для задачи со случайными входами представлены результаты вероятностного анализа двух алгоритмов, использующих эвристики “Иди в удаленный город” и “Склейка контуров”. Ил. 3, библиогр. 30.