Approximation algorithms for solving the constrained arc routing problem in mixed graphs

•We consider the constrained arc routing problem in mixed graphs.•It is to determine a shortest tour T traversing each e between l(e) and u(e) times.•We design an (1 + 1/l_0)-approximation algorithm in O(n2m3logn) to solve this problem.•We also present two optimal algorithms to solve its special versions, respectively.

Given a mixed graph G with vertex set V, let E and A   denote the sets of edges and arcs, respectively. We use Q+Q+ and Z+Z+ to denote the sets of positive rational numbers and positive integers, respectively. For any connected mixed graph G=(V,E∪A;w;l,u)G=(V,E∪A;w;l,u) with a length function w:E∪A→Q+w:E∪A→Q+ and two integer functions l,u:E∪A→Z+l,u:E∪A→Z+ satisfying l(e)⩽u(e)l(e)⩽u(e) for each e∈E∪Ae∈E∪A, we are asked to determine a minimum length tour T   traversing each e∈E∪Ae∈E∪A at least l(e)l(e) and at most u(e)u(e) times. This new constrained arc routing problem generalizes the mixed Chinese postman problem. Let n=|V|n=|V| and m=|E∪A|m=|E∪A| denote the number of vertices and edges (including arcs), respectively. Using network flow techniques, we design a (1+1/l0)(1+1/l0)-approximation algorithm in time O(n2m3logn) to solve this constrained arc routing problem such that l(e)