Approximation algorithms for solving the heterogeneous Chinese postman problem

In this paper, we consider the heterogeneous Chinese postman problem (the HCPP), which generalizes the k-Chinese postman problem. Specifically, given a weighted graph $$G=(V,E;w;r)$$ G = ( V , E ; w ; r ) with length function $$w:E\rightarrow R^{+}$$ w : E → R + satisfying the triangle inequality, a fixed depot $$r\in V$$ r ∈ V , and k vehicles having k nonuniform speeds $$\lambda _{1}, \lambda _{2}, \ldots ,\lambda _{k}$$ λ 1 , λ 2 , … , λ k , respectively, it is asked to find k tours in G for these k vehicles, each starting at the same depot r, and collectively traversing each edge in E at least once. The objective is to minimize the maximum completion time of vehicles, where the completion time of a vehicle is its total travel length divided by its speed. The main contribution of our paper is to show the following two results. (1) Given any small constant $$\delta >0$$ δ > 0 , we design a $$20.8765(1+\delta )$$ 20.8765 ( 1 + δ ) -approximation algorithm to solve the HCPP, where the running time required is bounded by a polynomial in the input size and $$\frac{1}{\delta }$$ 1 δ . (2) We present a $$(1+\varDelta -1/k)$$ ( 1 + Δ - 1 / k ) -approximation algorithm to solve the HCPP in cubic time, where $$\varDelta $$ Δ is the ratio of the largest vehicle speed to the smallest one.