Приближенные алгоритмы для задач о двух коммивояжерах и о двух цикловых покрытиях на максимум с двумя весовыми функциями
Ключевые слова:
Задача коммивояжера, Задача об m коммивояжерах, Задача о цикловом покрытии, приближенный алгоритм, гарантированная оценка точности, весовая функцияАннотация
В работе исследуются полиномиальные приближенные алгоритмы для задач о двух коммивояжерах и о двух цикловых покрытиях на максимум. Задача об m коммивояжерах (m-PSP) является естественным обобщением классической задачи коммивояжера и состоит в поиске m гамильтоновых циклов без общих ребер с минимальным или максимальным суммарным весом в полном взвешенном графе G = (V,E). Задача об m цикловых покрытиях заключается в нахождении m реберно непересекающихся цикловых покрытий с минимальным или максимальным суммарным весом в поном взвешенном графе. Множество точных и приближенных алгоритмов было предложено для задачи m-PSP в предположении, что во входном графе задана только одна весовая функуия ребер w : E -> R+, и суммарный вес гамильтоновых циклов H1. H2, ... , Hm определяется как w(H1) + w(H2) + ... + w(Hm). В то же время крайне мало таких алгоритмов известно для случая, когда во входном графе заданы m раличных веслвых функций w1, w2, ... , wm : E -> R+, и вес гамильтоновых циклов H1. H2, ... , Hm определяется как w1(H1) + w2(H2) + ... + wm(Hm) (задача m-PSP-mW). В настоящей статье представлена серия полиномиальных приближенных алгоритмов для задачи 2-PSP-2W на максимум с гарантированными оценками точности 1/2 и выше. В качестве сопутствующего результата, разработан полиномиальный приближенный алгоритм для задачи о двух цикловых покрытиях на максимум с двумя весовыми функциями, имеющий асимптотическую оценку точности 2/3.
