The Windy Postman Problem (WPP) is defined as follows: Given an undirected connected graph G=(V,E) and costs cij and cji for each edge ij∈E (where cij is the cost of traversing edge ij from i to j), find a windy postman tour of minimum cost. Here, by a windy postman tour, we mean a closed directed walk which is an orientation of a closed walk in G containing each edge of E at least once. This paper shows that the WPP can be solved in polynomial time for Eulerian graphs, and gives a complete description of the windy postman polyhedron for this class of graphs. Based on the solvability of the WPP on Eeulerian graphs, it designs an approximation algorithm for the problem on general graphs and shows that the value of the solution found by this algorithm is at most twice the optimum. A polynomial time algorithm and a complete description of the corresponding polytope fo the minimum cost Eulerian orientation problem are also presented.
