EN|RU

Volume 21, No 6, 2014, P. 11-20

UDC 519.172.2
A. N. Glebov, D. Zh. Zambalaeva and A. A. Skretneva  
2/3-approximation algorithm for the maximization version of the asymmetric two peripatetic salesman problem

Abstract:
We present a polynomial approximation algorithm for the maximization version of the asymmetric two peripatetic salesman problem which consists in finding two edge-disjoint Hamiltonian circuits of maximum total weight in a complete weighted digraph. The algorithm guarantees an approximation ratio of 2/3 in cubic running time.
Ill. 5, bibliogr. 7.

Keywords: traveling salesman problem, peripatetic salesman problem, polynomial algorithm, guaranteed ratio, directed graph.

Glebov Alexey Nikolaevich 1
Zamabalaeva Dolgor Zhamyanovna 1

Skretneva Anastasia Andreevna 1
1. S. L. Sobolev Institute of Mathematics, SB RAS,
4 Acad. Koptyug Ave., 630090 Novosibirsk, Russia
e-mail: angle@math.nsc.ru, dolgorzam@gmail.com, skretneva@gmail.com

 © Sobolev Institute of Mathematics, 2015