A 3/2-approximation algorithm for the multiple Hamiltonian path problem with no prefixed endpoints

Jun Wu (1, 2) , Yongxi Cheng (1, 2) , Zhen Yang (1, 2) , Feng Chu (3)

1 School of Management
2 State key laboratory for manufacturing systems engineering
3 IBISC - Informatique, BioInformatique, Systèmes Complexes

We study the multiple Hamiltonian path problem (MHPP) defined on a complete undirected graph G with n vertices. The edge weights of G are non-negative and satisfy the triangle inequality. The MHPP seeks to find a collection of k paths with exactly one visit to each vertex of G with the minimum total edge weight, where endpoints of the paths are not prefixed. We present a 3/2-approximation algorithm for MHPP with time complexity O(n3) for arbitrary k≥1.

Keywords: Approximation algorithm; Christofides heuristic; Multiple Hamiltonian path problem

Domains: Operations Research [math.OC]

Jun Wu, Yongxi Cheng, Zhen Yang, Feng Chu. A 3/2-approximation algorithm for the multiple Hamiltonian path problem with no prefixed endpoints. Operations Research Letters, 2023, 51 (5), pp.473--476. ⟨10.1016/j.orl.2023.07.003⟩. ⟨hal-04180029⟩