scientific article; zbMATH DE number 6007907

MaRDI QIDQ3115273zbMATH OpenFDO

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

Publication date 20 February 2012

zbMATH Keywords

2-peripatetic salesman problemguaranteed approximation ratiomax TSPpolynomial algorithmtraveling salesman problem

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35)

Recommendations

• A polynomial algorithm with approximation ratio 2/3 for the Asymmetric Maximum 2-Peripatetic Salesman Problem
• A 7/9 - Approximation Algorithm for the Maximum Traveling Salesman Problem
• Approximation algorithms for the maximum 2-peripatetic salesman problem
• scientific article; zbMATH DE number 4083394
• A polynomial algorithm for a constrained 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
• The traveling salesman problem: new polynomial approximation algorithms and domination analysis
• Approximating the metric 2-peripatetic salesman problem
• Approximation algorithms for the 2-peripatetic salesman problem with edge weights 1 and 2

Cited in

(12)

• A 2-approximation algorithm for the metric 2-peripatetic salesman problem
• 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
• A 7/9 - Approximation Algorithm for the Maximum Traveling Salesman Problem
• A polynomial 3/5-approximate algorithm for the asymmetric maximization version of the 3-PSP
• Combinatorial algorithms with performance guarantees for finding several Hamiltonian circuits in a complete directed weighted graph
• 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
• A polynomial algorithm with approximation ratio 2/3 for the Asymmetric Maximum 2-Peripatetic Salesman Problem
• An asymptotically optimal algorithm for the m-peripatetic salesman problem on random inputs with discrete distribution
• Approximation algorithms for 2-PSP-2W-max and 2-CC-2W-max
• \(7/5\)-approximation algorithm for 2-PSP on minimum with different weight functions

This page was built for publication:

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