ERROR ESTIMATION OF THE APPROXIMATION ALGORITHM FOR THE WINDY POSTMAN PROBLEM

摘要

If we restrict the postman to traversing each edge at most twice in the windypostman problem (WPP), we will get a new problem: 2WPP. An approximation algorithmhas been posed by M. Guan for the WPP. In the present paper, we improve the estimatederror given by M. Guan and show that we can estimate the error for the 2WPP by findinga minimum cost circulation. We also pose a new sufficient condition for the equivalencebetween WPP and 2WPP, which can be checked in polynomial time steps.