Approximation algorithms for 2-PSP-2W-max and 2-CC-2W-max
DOI10.33048/SEMI.2023.20.056zbMATH Open1543.90257MaRDI QIDQ6587426
Glebov Aleksey Glebov, Surèna Garmazhapovna Toktokhoeva, Lylova Sophya Lylova
Publication date: 14 August 2024
Published in: Sibirskie Elektronnye Matematicheskie Izvestiya (Search for Journal in Brave)
weight functionapproximation algorithmtraveling salesman problemguaranteed approximation ratiocycle cover problem2-perpatetic salesman problem
Programming involving graphs or networks (90C35) Combinatorial optimization (90C27) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)
Cites Work
- On the asymptotic optimality of an algorithm for solving the maximum \(m\)-PSP in a multidimensional Euclidean space
- \(7/5\)-approximation algorithm for 2-PSP on minimum with different weight functions
- A branch and bound algorithm for symmetric 2-peripatetic salesman problems
- A 4/5 -- approximation algorithm for the maximum traveling salesman problem
- An Algorithm with Approximation Ratio 5/6 for the Metric Maximum m-PSP
- Bounds for the symmetric 2-peripatetic salesman problem
- A polynomial algorithm with approximation ratio 2/3 for the Asymmetric Maximum 2-Peripatetic Salesman Problem
- Lower bounds for symmetricK-peripatetic salesman problems
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
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)
