Approximation algorithms for the asymmetric postman problem

We give a constant-factor approximation algorithm for the asymmetric traveling salesman problem. Our approximation guarantee is analyzed with respect to the standard LP relaxation, and thus our result confirms the conjectured constant integrality gap of ...

Given a network $${\mathcal {G}}=({\mathcal {V}},{\mathcal {E}})$$G=(V,E) of nodes denoted by $${\mathcal {V}}$$V, edges between nodes represented by $${\mathcal {E}}$$E, and costs associated with the edges, postman problem (PP) is to find the route ...

The windy postman problem is the NP-hard problem of finding the minimum cost of a tour traversing all edges of an undirected graph, where the cost of an edge depends on the direction of traversal. Given an undirected graph G, we consider the polyhedron ...