An approximation algorithm for the minimum two peripatetic salesmen problem with different weight functions |
| |
| Authors: | A. N. Glebov D. Zh. Zambalaeva |
| |
| Affiliation: | 1.Sobolev Institute of Mathematics,Novosibirsk,Russia;2.Novosibirsk State University,Novosibirsk,Russia |
| |
| Abstract: | ![]()
We present a polynomial algorithm with time complexity O(n 5) and approximation ratio 4/3 (plus some additive constant) for the minimum 2-peripatetic salesman problem in a complete n-vertex graph with different weight functions valued 1 and 2 (abbreviated to as 2-PSP(1, 2)-min-2w). This result improves the available algorithm for this problem with approximation ratio 11/7. |
| |
| Keywords: | |
| 本文献已被 SpringerLink 等数据库收录！ |
