TY - JOUR

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

AU - Nikolaevich, Glebov Aleksey

AU - Sergeevna, Lylova Sophya

AU - Garmazhapovna, Toktokhoeva Surena

N1 - Глебов А.Н., Лылова С.С., Токтохоева С.Г. Приближенные алгоритмы для задач о двух коммивояжерах и о двух цикловых покрытиях на максимум с двумя весовыми функциями // Сибирские электронные математические известия. – 2023. – Т. 20, № 2. – С. 923-941. Работа выполнена в рамках государственного задания ИМ СО РАН (проект № FWNF-2022-0017).

PY - 2023

Y1 - 2023

N2 - 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 find m edge disjoint Hamiltonian cycles of the extremal total weight in a complete weighted graph G = (V, E). In the m-Cycle Cover Problem (m-CC), we need to find 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 T R+ and the weight of m Hamiltonian cycles H、，Hz,…,Hm is defined as w(Hi) +… + w(Hm). However, not so many results are known for the case when we are given m distinct weight functions wi, W2,…, wm and the weight of Hi,H2,…, Hm is defined as wi(Hi) + 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 | for the 2-CC-max-2W problem.

AB - 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 find m edge disjoint Hamiltonian cycles of the extremal total weight in a complete weighted graph G = (V, E). In the m-Cycle Cover Problem (m-CC), we need to find 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 T R+ and the weight of m Hamiltonian cycles H、，Hz,…,Hm is defined as w(Hi) +… + w(Hm). However, not so many results are known for the case when we are given m distinct weight functions wi, W2,…, wm and the weight of Hi,H2,…, Hm is defined as wi(Hi) + 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 | for the 2-CC-max-2W problem.

KW - 2-Perpatetic Salesman Prob-lem

KW - Cycle Cover Problem

KW - Traveling Salesman Problem

KW - approximation algorithm

KW - guaranteed approxi-mation ratio

KW - weight function

UR - https://www.scopus.com/record/display.uri?eid=2-s2.0-85188437003&origin=inward&txGid=db6d5ba2395408448a55edb773d96f7b

UR - https://www.mendeley.com/catalogue/3e2f663c-2756-389a-aeac-676dfedab156/

U2 - 10.33048/semi.2023.20.056

DO - 10.33048/semi.2023.20.056

M3 - статья

VL - 20

SP - 923

EP - 941

JO - Сибирские электронные математические известия

JF - Сибирские электронные математические известия

SN - 1813-3304

IS - 2

ER -