A. N. Glebov, D. Zh. Zambalayeva, “Polynomial algorithm with approximation ratio <nobr>$7/9$</nobr> for maximum 2-PSP”, Diskretn. Anal. Issled. Oper., 2011, Volume 18, Issue 4,Pages <nobr>17

This article is cited in 16 papers

Polynomial algorithm with approximation ratio $7/9$ for maximum 2-PSP

A. N. Glebov^ab, D. Zh. Zambalayeva^a

^a S. L. Sobolev Institute of Mathematics, SB RAS, Novosibirsk, Russia
^b Novosibirsk State University, Novosibirsk, Russia

Abstract: We study a 2-peripatetic salesman problem on maximum which consists in finding two edge-disjoint Hamiltonian cycles of maximum total weight in a complete undirected graph. We present a cubic time approximation algorithm for this problem with guaranteed ratio $7/9$, the best known for today. Ill. 5, bibliogr. 14.

Keywords: traveling salesman problem, 2-peripatetic salesman problem, polynomial algorithm, guaranteed approximation ratio.

UDC: 519.8

Received: 25.01.2011
Revised: 06.05.2011