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 ∪ 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 ∪ A | is the number of links of G, respectively. We obtain the following four main results. (1) Given any two constants $$\beta \ge 1$$ β ≥ 1 and $$\alpha \ge 1$$ α ≥ 1 , we prove that there is no polynomial-time algorithm with approximation ratios $$(1,\beta )$$ ( 1 , β ) or $$(\alpha , 1)$$ ( α , 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}}}$$ A to solve the VtcMCP problem in time $$O(m^{2}\log n)$$ O ( m 2 log n ) ; (3) We prove the fact that this algorithm $${{\mathcal {A}}}$$ A in (2) is indeed an exact algorithm to optimally solve the VtcMCP problem for the case $$E=\emptyset $$ E = ∅ ; (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 = ∅ .