|
Sibirskie Èlektronnye Matematicheskie Izvestiya [Siberian Electronic Mathematical Reports], 2011, Volume 8, Pages 296–309
(Mi semr325)
|
|
|
|
This article is cited in 5 scientific papers (total in 5 papers)
7/5-approximation algorithm for 2-PSP on minimum with different weight functions
A. N. Glebova, A. V. Gordeevab, D. Zh. Zambalayevaa a Sobolev Institute of Mathematics, Siberian Branch of the Russian Academy of Sciences, Novosibirsk
b Novosibirsk State University
Abstract:
We present a cubic time algorithm with approximation ratio 7/5 (plus some additive constant) for the 2-Peripatetic Salesman Problem on minimum with different weight functions valued 1 and 2 (abbreviated to as 2-PSP(1,2)-min-2w). Our result improves the other known algorithm for this problem which has approximation ratio 11/7.
Keywords:
Traveling Salesman Problem, 2-Peripatetic Salesman Problem, polynomial algorithm, guaranteed approximation ratio.
Received August 29, 2011, published October 11, 2011
Citation:
A. N. Glebov, A. V. Gordeeva, D. Zh. Zambalayeva, “7/5-approximation algorithm for 2-PSP on minimum with different weight functions”, Sib. Èlektron. Mat. Izv., 8 (2011), 296–309
Linking options:
https://www.mathnet.ru/eng/semr325 https://www.mathnet.ru/eng/semr/v8/p296
|
Statistics & downloads: |
Abstract page: | 367 | Full-text PDF : | 59 | References: | 40 |
|