A polynomial 3/5-approximate algorithm for the asymmetric maximization version of the 3-PSP

DOI10.1134/S1990478919020042zbMATH Open1438.90284OpenAlexW2952489944MaRDI QIDQ4973249FDOQ4973249

Authors: Surèna Garmazhapovna Toktokhoeva, A. N. Glebov 

Publication date: 2 December 2019

Published in: Journal of Applied and Industrial Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1134/s1990478919020042

Recommendations

• A polynomial algorithm with approximation ratio 2/3 for the Asymmetric Maximum 2-Peripatetic Salesman Problem
• A polynomial algorithm with asymptotic ratio \(2/3\) for the asymmetric maximization version of the \(m\)-PSP
• Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
• Combinatorial algorithms with performance guarantees for finding several Hamiltonian circuits in a complete directed weighted graph
• 35/44-Approximation for Asymmetric Maximum TSP with Triangle Inequality

zbMATH Keywords

approximation algorithmHamiltonian cycletraveling salesman problem\(m\)-peripatetic salesman problemguaranteed approximation ratio

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Approximation algorithms (68W25)

Cites Work

• Better approximations for max TSP
• The traveling salesman problem and its variations
• An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
• A branch and bound algorithm for symmetric 2-peripatetic salesman problems
• A 7/9 - Approximation Algorithm for the Maximum Traveling Salesman Problem
• Title not available (Why is that?)
• Title not available (Why is that?)
• Bounds for the symmetric 2-peripatetic salesman problem
• Well-solved cases of the 2-peripatetic salesman problem
• 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
• Asymptotically optimal algorithm for finding one and two edge-disjoint traveling salesman routes of maximal weight in Euclidean space
• A heuristic approach to the overnight security service problem
• Approximation algorithms for asymmetric TSP by decomposing directed regular multigraphs
• Title not available (Why is that?)
• A 2-approximation algorithm for the metric 2-peripatetic salesman problem
• Approximation algorithms for solving the 2-peripatetic salesman problem on a complete graph with edge weights 1 and 2
• Title not available (Why is that?)
• An approximation algorithm for the minimum 2-peripatetic salesman problem with different weight functions
• Approximation algorithms for the maximum 2-peripatetic salesman problem
• \(7/5\)-approximation algorithm for 2-PSP on minimum with different weight functions
• A 4/5 -- approximation algorithm for the maximum traveling salesman problem
• Title not available (Why is that?)
• 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

Cited In (1)

• A polynomial algorithm with asymptotic ratio $2/3$ for the asymmetric maximization version of the $m$-PSP

This page was built for publication: A polynomial 3/5-approximate algorithm for the asymmetric maximization version of the 3-PSP

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