Constant factor approximation algorithm for TSP satisfying a biased triangle inequality

In this paper, we study the approximability of a variant of the Traveling Salesman Problem called the Biased-TSP. In the Biased-TSP, the edge cost function violates the triangle inequality in a “controlled” manner. We give a 72-factor approximation algorithm for this problem by a suitable modification of the double-tree heuristic.