Приближенный алгоритм для метрической постановки задачи о цикловом покрытии графа
Аннотация
Ратнер Е.Б. Приближенный алгоритм для метрической постановки задачи о цикловом покрытии графа, выпускнаяквалификационная работа, стр. 21, рис. 3, табл. 1.
Ключевые слова: цикловое покрытие, приближенный алгоритм, задача коммивояжера, гамильтонов цикл, фактор аппроксимации, NP-трудная задача.
В работе обсуждается труднорешаемость задачи о цикловом покрытии графа, рассматриваются 2-приближенный и 3/2-приближенный алгоритмы решения метрической постановки задачи коммивояжера, производится их модификация для метрической постановки задачи о цикловом покрытии графа. Для каждой из модификаций показывается сохранение фактора аппроксимации, если это возможно, либо находится контрпример, показывающий обратное.
Ключевые слова: цикловое покрытие, приближенный алгоритм, задача коммивояжера, гамильтонов цикл, фактор аппроксимации, NP-трудная задача.
В работе обсуждается труднорешаемость задачи о цикловом покрытии графа, рассматриваются 2-приближенный и 3/2-приближенный алгоритмы решения метрической постановки задачи коммивояжера, производится их модификация для метрической постановки задачи о цикловом покрытии графа. Для каждой из модификаций показывается сохранение фактора аппроксимации, если это возможно, либо находится контрпример, показывающий обратное.