On the Windy Postman Problem on eulerian graphs

Abstract

The Windy Postman Problem (WPP) is defined as follows: Given an undirected connected graphG = (V, E) and costsc _ij andc _ji for each edgeij ∈E (wherec _ij is the cost of traversing edgeij fromi toj), 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 inG containing each edge ofE at least once.

We show in this paper that the WPP can be solved in polynomial time for Eulerian graphs, and we give a complete description of the windy postman polyhedron for this class of graphs. Based on the solvability of the WPP on Eulerian graphs, we design an approximation algorithm for the problem on general graphs and show 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 for the minimum cost Eulerian orientation problem are also presented.