Given a mixed graph G with vertex set V, let E and A denote the sets of edges and arcs, respectively. We use Q + and 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 ) with a length function w : E ∪ A → Q + and two integer functions l , u : E ∪ A → Z + satisfying l ( e ) ⩽ u ( e ) for each e ∈ E ∪ A , we are asked to determine a minimum length tour T traversing each e ∈ E ∪ A at least l ( e ) and at most u ( e ) times. This new constrained arc routing problem generalizes the mixed Chinese postman problem. Let n = | V | and m = | E ∪ A | denote the number of vertices and edges (including arcs), respectively. Using network flow techniques, we design a ( 1 + 1 / l 0 ) -approximation algorithm in time O ( n 2 m 3 log n ) to solve this constrained arc routing problem such that l ( e ) < u ( e ) holds for each edge e ∈ E , l ( e ) ⩽ u ( e ) holds for each arc e ∈ A and l 0 = min { l ( e ) | e ∈ E } . In addition, we present two optimal combinatorial algorithms in times O ( n 3 ) and O ( nm 2 log n ) to solve this problem for the cases A = ∅ and E = ∅ , respectively. 
Approximation algorithms for solving the constrained arc routing problem in mixed graphs