文献类型：期刊文献

英文题名：Approximation algorithms for the k-depots Hamiltonian path problem

作者：Yang, Yichen[1];Liu, Zhaohui[1];Yu, Wei[1]

机构：[1]East China Univ Sci & Technol, Dept Math, Shanghai 200237, Peoples R China

年份：2022

卷号：16

期号：4

起止页码：1215

外文期刊名：OPTIMIZATION LETTERS

收录：;EI(收录号：20212710579309);WOS:【SCI-EXPANDED(收录号:WOS:000668412200001)】；

基金：This research is supported by the National Natural Science Foundation of China under grant number 11671135 and the Natural Science Foundation of Shanghai under grant number 19ZR1411800.

语种：英文

外文关键词：Hamiltonian path problem; Approximation algorithm; Multiple salesmen; Multiple depots; Christofides-like heuristic

摘要：We consider a multiple-depots extension of the classic Hamiltonian path problem where k salesmen are initially located at different depots. To the best of our knowledge, no algorithm for this problem with a constant approximation ratio has been previously proposed, except for some special cases. We present a polynomial algorithm with a tight approximation ratio of max {3/2, 2 - 1/k} for arbitrary k >= 1, and an algorithm with approximation ratio 5/3 that runs in polynomial time for fixed k. Moreover, we develop a recursive framework to improve the approximation ratio to 3/2 + epsilon. This framework is polynomial for fixed k and epsilon, and may be useful in improving the Christofides-like heuristics for other related multiple salesmen routing problems.