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 ( n 2 m 3 log n ) to solve this problem. We also present two optimal algorithms to solve its special versions, respectively.
approximation algorithm arc routing combinatorial optimization lower/upper demand bound combinatorial algorithm