A polynomial algorithm with approximation ratio 2/3 for the Asymmetric Maximum 2-Peripatetic Salesman Problem

DOI10.1134/S199047891501007XzbMATH Open1324.90182OpenAlexW2088833374MaRDI QIDQ5264766FDOQ5264766

Authors: D. Zh. Zambalaeva, A. A. Skretneva, A. N. Glebov 

Publication date: 27 July 2015

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

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

Recommendations

• scientific article
• A polynomial algorithm with asymptotic ratio \(2/3\) for the asymmetric maximization version of the \(m\)-PSP
• Approximation algorithms for the maximum 2-peripatetic salesman problem
• FIXED RATIO POLYNOMIAL TIME APPROXIMATION ALGORITHM FOR THE PRIZE-COLLECTING ASYMMETRIC TRAVELING SALESMAN PROBLEM
• A Polyhedral Approach to the Asymmetric Traveling Salesman Problem
• A 2-approximation algorithm for the metric 2-peripatetic salesman problem
• A 2-Approximation Algorithm for the Metric 2-Peripatetic Salesman Problem
• An O(logn) Approximation Ratio for the Asymmetric Traveling Salesman Path Problem
• scientific article; zbMATH DE number 5899262
• A branch and bound algorithm for symmetric 2-peripatetic salesman problems

zbMATH Keywords

traveling salesman problemdirected graphpolynomial algorithm2-peripatetic salesman problemguaranteed accuracy bound

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Combinatorial optimization (90C27)

Cites Work

• A branch and bound algorithm for symmetric 2-peripatetic salesman problems
• A 7/9 - Approximation Algorithm for the Maximum Traveling Salesman Problem
• Bounds for the symmetric 2-peripatetic salesman problem
• Lower bounds for symmetricK-peripatetic salesman problems
• Approximation algorithms for asymmetric TSP by decomposing directed regular multigraphs
• Title not available (Why is that?)

Cited In (5)

• A polynomial algorithm with asymptotic ratio $2/3$ for the asymmetric maximization version of the $m$-PSP
• An approximation algorithm for the minimum 2-peripatetic salesman problem with different weight functions
• A Polynomial 3/5-Approximate Algorithm for the Asymmetric Maximization Version of the 3-PSP
• Approximation algorithms for 2-PSP-2W-max and 2-CC-2W-max
• Title not available (Why is that?)

This page was built for publication: A polynomial algorithm with approximation ratio 2/3 for the Asymmetric Maximum 2-Peripatetic Salesman Problem

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