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 ∪ A ; w , b) with length function w (·) on edges and arcs and traversal function 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 | is the number of vertices and m = | E ∪ A | is the number of links of G, respectively. We obtain the following four main results. (1) Given any two constants β ≥ 1 and α ≥ 1 , we prove that there is no polynomial-time algorithm with approximation ratios (1 , β) or (α , 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 A to solve the VtcMCP problem in time O (m 2 log n) ; (3) We prove the fact that this algorithm A in (2) is indeed an exact algorithm to optimally solve the VtcMCP problem for the case E = ∅ ; (4) We present an exact algorithm to optimally solve the VtcMCP problem in time O (m 3) for the case A = ∅ . [ABSTRACT FROM AUTHOR]