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

DOI10.1134/S199047891501007XzbMATH Open1324.90182OpenAlexW2088833374MaRDI QIDQ5264766FDOQ5264766

A. A. Skretneva, D. Zh. Zambalaeva, 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

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

• Title not available (Why is that?)
• 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

Cited In (4)

• A polynomial algorithm with asymptotic ratio $2/3$ for the asymmetric maximization version of the $m$-PSP
• 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?)

   Recommendations

• Title not available (Why is that?) 👍 👎
• 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 👍 👎
• Title not available (Why is that?) 👍 👎
• A 2-Approximation Algorithm for the Metric 2-Peripatetic Salesman Problem 👍 👎
• An O(logn) Approximation Ratio for the Asymmetric Traveling Salesman Path Problem 👍 👎
• Title not available (Why is that?) 👍 👎
• A branch and bound algorithm for symmetric 2-peripatetic salesman problems 👍 👎

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)