Name
Abstract | ||
|---|---|---|
In this paper, we study a multiple-terminal extension of the classic Hamiltonian path problem where m salesmen are initially located at different depots and finally stopped at different terminals. To the best of our knowledge, only 2-approximation algorithm is available in the literature. For arbitrary m⩾2, we first present a Christofides-like heuristic with a tight approximation ratio of 2−12m+1. Besides, we also develop a (53+ϵ)-approximation algorithm by divide-and-conquer technique. The (53+ϵ)-approximation algorithm runs in polynomial time for fixed m and ϵ. |
Year | DOI | Venue |
|---|---|---|
2019 | 10.1016/j.disopt.2019.05.002 | Discrete Optimization |
Keywords | Field | DocType |
Hamiltonian path problem,Approximation algorithm,Constrained forest,Matroid | Approximation algorithm,Discrete mathematics,Heuristic,Hamiltonian path problem,Depot,Time complexity,Mathematics | Journal |
Volume | ISSN | Citations |
34 | 1572-5286 | 0 |
PageRank | References | Authors |
0.34 | 0 | 2 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Yichen Yang | 1 | 0 | 0.34 |
| Zhaohui Liu | 2 | 36 | 4.45 |