Approximation algorithms for the maximum 2-peripatetic salesman problem

DOI10.1134/S1990478912030040MaRDI QIDQ5263758zbMATH OpenFDO

Authors Eh. Kh. Gimadi, E. V. Ivonina

Publication date 17 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/S1990478912030040

zbMATH Keywords

traveling salesman problempolynomial algorithmguaranteed approximation ratio2-peripatetic salesman problem

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Combinatorial optimization (90C27)

Recommendations

• Approximation algorithms for solving the 2-peripatetic salesman problem on a complete graph with edge weights 1 and 2
• scientific article; zbMATH DE number 6007907
• Approximation algorithms for the 2-peripatetic salesman problem with edge weights 1 and 2
• A polynomial algorithm with approximation ratio 2/3 for the Asymmetric Maximum 2-Peripatetic Salesman Problem
• Approximating the metric 2-peripatetic salesman problem

Cited in

(19)

• Approximation algorithms for solving the 2-peripatetic salesman problem on a complete graph with edge weights 1 and 2
• An approximation algorithm for the minimum 2-peripatetic salesman problem with different weight functions
• Approximation algorithms for 2-PSP-2W-max and 2-CC-2W-max
• On the generalized 2-peripatetic salesman problem
• An asymptotically optimal algorithm for the m-peripatetic salesman problem on random inputs with discrete distribution
• On the \(m\)-capacitated peripatetic salesman problem with capacity restrictions
• scientific article; zbMATH DE number 2159162 (Why is no real title available?)
• The undirected \(m\)-capacitated peripatetic salesman problem
• A polynomial algorithm with asymptotic ratio 2/3 for the asymmetric maximization version of the m-PSP
• Sensitivity analysis for symmetric 2-peripatetic salesman problems
• A polynomial 3/5-approximate algorithm for the asymmetric maximization version of the 3-PSP
• A 2-Approximation Algorithm for the Metric 2-Peripatetic Salesman Problem
• On 2-capacitated peripatetic salesman problem with different weight functions
• Approximation algorithms for the 2-peripatetic salesman problem with edge weights 1 and 2
• scientific article; zbMATH DE number 6007907 (Why is no real title available?)
• A polynomial algorithm with approximation ratio 2/3 for the Asymmetric Maximum 2-Peripatetic Salesman Problem
• Combinatorial algorithms with performance guarantees for finding several Hamiltonian circuits in a complete directed weighted graph
• Safe and secure vehicle routing: a survey on minimization of risk exposure
• Approximating the metric 2-peripatetic salesman problem

This page was built for publication: Approximation algorithms for the maximum 2-peripatetic salesman problem

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