Approximation algorithms for solving the vertex-traversing-constrained mixed Chinese postman problem

In this paper, we address the vertex-traversing-constrained mixed Chinese postman problem (the VtcMCP problem), which is a further generalization of the Chinese postman problem, and this new problem has many practical applications in real life. Specifically, given a connected mixed graph \(G=(V, E\cup A; w,b)\) $G=(V,E\cup A;w,b)$ with length function \(w(\cdot )\) $w(·)$ on edges and arcs and traversal function \(b(\cdot )\) $b(·)$ on vertices, we are asked to determine a tour traversing each link (i.e., either edge or arc) at least once and each vertex v at most b(v) times, the objective is to minimize the total length of such a tour, where \(n=|V|\) $n=|V|$ is the number of vertices and \(m=|E\cup A|\) $m=|E\cup A|$ is the number of links of G, respectively. We obtain the following four main results. (1) Given any two constants \(\beta \ge 1\) $\beta \ge 1$ and \(\alpha \ge 1\) $\alpha \ge 1$ , we prove that there is no polynomial-time algorithm with approximation ratios \((1,\beta )\) $(1,\beta )$ or \((\alpha , 1)\) $(\alpha ,1)$ for solving the VtcMCP problem, where an (h, k)-approximation algorithm for solving the VtcMCP problem is one algorithm that produces a solution with violating the vertex-traversing constraints by at most a ratio of h and with costing at most k times the optimal value; (2) We design a (3, 2)-approximation algorithm \({{\mathcal {A}}}\) $\mathcal{A}$ to solve the VtcMCP problem in time \(O(m^{2}\log n)\) $O(m^{2}logn)$ ; (3) We prove the fact that this algorithm \({{\mathcal {A}}}\) $\mathcal{A}$ in (2) is indeed an exact algorithm to optimally solve the VtcMCP problem for the case \(E=\emptyset \) $E=\mathrm{\varnothing }$ ; (4) We present an exact algorithm to optimally solve the VtcMCP problem in time \(O(m^{3})\) $O(m^3)$ for the case \(A=\emptyset \) $A=\mathrm{\varnothing }$ .