A heuristic with worst-case analysis for minimax routing of two travelling salesmen on a tree

被引：54

作者：

Averbakh, I

Berman, O

机构：

[1] UNIV TORONTO,DIV MANAGEMENT & ECON SCARBOROUGH,TORONTO,ON M5S 1V4,CANADA

[2] UNIV TORONTO,FAC MANAGEMENT,TORONTO,ON M5S 1V4,CANADA

来源：

DISCRETE APPLIED MATHEMATICS | 1996年 / 68卷 / 1-2期

关键词：

travelling salesman problem; algorithms; worst-case analysis;

D O I：

10.1016/0166-218X(95)00054-U

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

Suppose two travelling salesmen must visit together all points/nodes of a tree, and the objective is to minimize the maximal length of their tours. Home locations of the salesmen are given, and it is required to find optimal tours. For this NP-hard problem a heuristic with complexity O(n) is presented. The worst-case relative error for the heuristic performance is 1/3 for the case of equal home locations for both servers and 1/2 for the case of different home locations.

引用

页码：17 / 32

页数：16