Приближенные алгоритмы с фиксированными оценками точности для серии асимметричных задач маршрутизации

Обосновываются первые алгоритмы с константными оценками точности для серии асимметричных постановок задач маршрутизации: задачи о штейнеровском цикле, задачи коммивояжера с призами, задачи о покрытии графа ограниченным числом циклов и др. В большинстве своем предложенные алгоритмы опираются на оригинальные схемы сведения исследуемых постановок к вспомогательным постановкам асимметричной задачи коммивояжера и прорывные результаты О. Свенссона, Я. Тарнавски, Л. Вега и В. Трауб, Й. Вигена в области эффективной аппроксимируемости данной задачи. Алгоритм для задачи о покрытии графа ограниченным числом циклов опирается на технику, связанную с более глубокой модификацией подхода Свенссона–Трауб.