Approximation algorithms for solving the 2-peripatetic salesman problem on a complete graph with edge weights 1 and 2 |
| |
Authors: | E. Kh. Gimadi Yu. V. Glazkov A. N. Glebov |
| |
Affiliation: | (1) Sobolev Institute of Mathematics, pr. Akad. Koptyuga 4, Novosibirsk, 630090, Russia |
| |
Abstract: | The problem of finding two disjoint Hamiltonian cycles of minimum sum weight is considered in a complete undirected graph with arbitrarily chosen weights of the edges 1 and 2. The main result of the paper is the presentation of polynomial algorithms with the currently best guaranteed performance factors 26/21 and 6/5. These algorithms are based on finding the partial tours with a large number of edges in the graphs of a special type. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |