Аннотация:
Недавние прорывные результаты Свенссона-Тарнавски-Вега и Трауб-Вигена в области аппроксимации асимметричной задачи коммивояжера (ATSP) в классе полиномиальных приближенных алгоритмов с фиксированными оценками точности создали предпосылки для обоснования эффективной аппроксимируемости широкого круга асимметричных задач комбинаторной оптимизации. Наряду с подходом Свенссона-Трауб, в сообщении обсуждаются развивающие его авторские результаты в области полиномиальных приближенных алгоритмов с фиксированными факторами аппроксимации для асимметричных версий задачи о штейнеровском цикле, задачи коммивояжера с призами, задачи оптимальной маршрутизации транспортных средств и др.
