7/5-approximation algorithm for 2-PSP on minimum with different weight functions

MaRDI QIDQ890881zbMATH OpenFDO

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

Publication date 16 November 2015

Published in Sibirskie Elektronnye Matematicheskie Izvestiya (Search for Journal in Brave)

Full work available at URL http://semr.math.nsc.ru/v8/p296-309.pdf

zbMATH Keywords

traveling salesman problempolynomial algorithmguaranteed approximation ratio2-peripatetic salesman problem

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Approximation algorithms (68W25) Abstract computational complexity for mathematical programming problems (90C60)

Recommendations

• An approximation algorithm for the minimum 2-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
• A 2-Approximation Algorithm for the Metric 2-Peripatetic Salesman Problem
• A 2-approximation algorithm for the metric 2-peripatetic salesman problem

Cited in

(5)

• 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
• 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
• Combinatorial algorithms with performance guarantees for finding several Hamiltonian circuits in a complete directed weighted graph

This page was built for publication: \(7/5\)-approximation algorithm for 2-PSP on minimum with different weight functions

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