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

zbMATH Open1329.90120MaRDI QIDQ890881FDOQ890881

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

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

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

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)

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
• 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)