Approximation algorithms for 2-PSP-2W-max and 2-CC-2W-max

DOI10.33048/SEMI.2023.20.056MaRDI QIDQ6587426zbMATH OpenFDO

Authors Glebov Aleksey Glebov, Lylova Sophya Lylova, Surèna Garmazhapovna Toktokhoeva

Publication date 14 August 2024

Published in Sibirskie Elektronnye Matematicheskie Izvestiya (Search for Journal in Brave)

Full work available at URL https://doi.org/10.33048/SEMI.2023.20.056

zbMATH Keywords

2-perpatetic salesman problemapproximation algorithmcycle cover problemguaranteed approximation ratiotraveling salesman problemweight function

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Combinatorial optimization (90C27) Programming involving graphs or networks (90C35)

Recommendations

• Approximation algorithms for the 2-peripatetic salesman problem with edge weights 1 and 2
• A 2-Approximation Algorithm for the Metric 2-Peripatetic Salesman Problem
• A 2-approximation algorithm for the metric 2-peripatetic salesman problem
• Approximation algorithms for the maximum 2-peripatetic salesman problem
• Approximation algorithms for solving the 2-peripatetic salesman problem on a complete graph with edge weights 1 and 2

Cites work

• \(7/5\)-approximation algorithm for 2-PSP on minimum with different weight functions
• A 2-approximation algorithm for the metric 2-peripatetic salesman problem
• A 4/5 -- approximation algorithm for the maximum traveling salesman problem
• A branch and bound algorithm for symmetric 2-peripatetic salesman problems
• A polynomial algorithm with approximation ratio 2/3 for the Asymmetric Maximum 2-Peripatetic Salesman Problem
• An algorithm with approximation ratio 5/6 for the metric maximum m-PSP
• An approximation algorithm for the minimum 2-peripatetic salesman problem with different weight functions
• Approximation algorithms for solving the 2-peripatetic salesman problem on a complete graph with edge weights 1 and 2
• Bounds for the symmetric 2-peripatetic salesman problem
• scientific article; zbMATH DE number 6007907 (Why is no real title available?)
• scientific article; zbMATH DE number 6004865 (Why is no real title available?)
• scientific article; zbMATH DE number 3910163 (Why is no real title available?)
• scientific article; zbMATH DE number 1518742 (Why is no real title available?)
• Lower bounds for symmetricK-peripatetic salesman problems
• On the asymptotic optimality of an algorithm for solving the maximum \(m\)-PSP in a multidimensional Euclidean space

This page was built for publication: Approximation algorithms for 2-PSP-2W-max and 2-CC-2W-max

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6587426)