3-Approximation algorithm for a two depot, heterogeneous traveling salesman problem

摘要

We present the first approximation algorithm for a two depot, heterogeneous traveling salesman problem with an approximation ratio of 3 when the costs are symmetric and satisfy the triangle inequality.