Реферат: We present new polynomial approximation algorithms for the 2-Perpatetic Salesman Problem and the 2-Cycle Cover Problem. The m-Perpatetic Salesman Problem (m-PSP) is a generalization of the classical Traveling Salesman Problem. In the m-PSP, we need to nd m edge disjoint Hamiltonian cycles of the extremal total weight in a complete weighted graph G = (VE). In the m-Cycle Cover Problem (m-CC), we need to nd m edge disjoint cycle covers of the extremal weight in G. Many exact and approximation algorithms were proposed for the case of m-PSP where we are given only one weight function w : E R+andthe weight of m Hamiltonian cycles H1, H2 ... Hm is de ned as w(H1)+ +w(Hm). However, not so many results are known for the case when we are given m distinct weight functions w1w2 wm and the weight of H1H2 Hm is de ned as w1(H1) + w2(H2) + +wm(Hm) (the m-PSP-mW problem). Here we present a series of polynomial algorithms with approximation ratios 1 2 and higher for the 2-PSP-max-2W. As a supporting result, we produce a polynomial algorithm with the asymptotic ratio 2 3 for the 2-CC-max-2W problem.

Библиографическая ссылка: Глебов А.Н. , Лылова С.С. , Токтохоева С.Г.
Приближенные алгоритмы для задач о двух коммивояжерах и о двух цикловых покрытиях на максимум с двумя весовыми функциями
Сибирские электронные математические известия (Siberian Electronic Mathematical Reports). 2025.

Даты:

Поступила в редакцию:

10 дек. 2022 г.

Идентификаторы БД: Нет идентификаторов

Цитирование в БД: Пока нет цитирований