Approximation Algorithms For Some Minimum Postmen Cover Problems

With the development and progress of the times,logistics dispatch,taxi dispatch,mechanical and manual dispatch play more and more important roles in society and enterprises,and have attracted the attention of many mathematicians and economists.These problems are on the arc routing.This paper mainly studies the minimum rural postman cover problem and the minimum Chinese postman cover problem.A graph decomposition algorithm is proposed,and approximate algorithms are given based on this.The MRPCP aims to cover a given subset R of edges of an undirected weighted graph G=(V,E)by a minimum size set of closed walks of bounded length A.The MCPCP is a special case of the MRPCP with R=E.First,we simply extended the approximation algorithms of cycle cover problems to obtain the 7-approximation algorithm for the MR-PCP.Then,considering the idea of tree decomposition is mainly used in the cycle cover problems,we considered and started it.A set of graph decomposition algorithms on gen-eral graphs.Based on this,we have obtained two 5-approximation algorithms of different complexity on the MRPCP.Finally,we also obtained a 4-approximation algorithm for the MCPCP.