Approximation algorithms for the k-depots Hamiltonian path problem

Autor: Wei Yu, Zhaohui Liu, Yichen Yang
Rok vydání: 2021
Předmět:
Zdroj: Optimization Letters. 16:1215-1234
ISSN: 1862-4480
1862-4472
Popis: 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 \left\{ \frac{3}{2},2-\frac{1}{k}\right\} $$ for arbitrary $$k\geqslant 1$$ , and an algorithm with approximation ratio $$\frac{5}{3}$$ that runs in polynomial time for fixed k. Moreover, we develop a recursive framework to improve the approximation ratio to $$\frac{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.
Databáze: OpenAIRE
Externí odkaz: