Abstract: 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.

Cite: Глебов А.Н. , Лылова С.С. , Токтохоева С.Г.
Приближенные алгоритмы для задач о двух коммивояжерах и о двух цикловых покрытиях на максимум с двумя весовыми функциями
Сибирские электронные математические известия (Siberian Electronic Mathematical Reports). 2023. Т.20. №2. С.923-941. DOI: 10.33048/semi.2023.20.056 Scopus РИНЦ

Dates:

Submitted:	Dec 10, 2022
Accepted:	Dec 12, 2023

Identifiers:

Scopus:	2-s2.0-85188437003
Elibrary:	82134643

Citing: Пока нет цитирований

Altmetrics: