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

2-peripatetic salesman problemguaranteed approximation ratiopolynomial algorithmtraveling 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 the 2-peripatetic salesman problem with edge weights 1 and 2
• On the generalized 2-peripatetic salesman problem
• The undirected \(m\)-capacitated peripatetic salesman problem
• Sensitivity analysis for symmetric 2-peripatetic salesman problems
• Approximating the metric 2-peripatetic salesman problem
• scientific article; zbMATH DE number 6007907 (Why is no real title available?)
• 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
• scientific article; zbMATH DE number 2159162 (Why is no real title available?)
• 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
• On the \(m\)-capacitated peripatetic salesman problem with capacity restrictions
• 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
• A 2-Approximation Algorithm for the Metric 2-Peripatetic Salesman Problem
• On 2-capacitated peripatetic salesman problem with different weight functions
• Safe and secure vehicle routing: a survey on minimization of risk exposure
• Approximation algorithms for 2-PSP-2W-max and 2-CC-2W-max

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)