Improved approximation algorithms for metric maximum ATSP and maximum 3-cycle cover problems

Abstract

We consider an APX-hard variant (Δ-Max-ATSP) and an APX-hard relaxation (Max-3-DCC) of the classical traveling salesman problem. Δ-Max-ATSP is the following problem: Given an edge-weighted complete loopless directed graph G such that the edge weights fulfill the triangle inequality, find a maximum weight Hamiltonian tour of G. We present 31/40-approximation algorithm for Δ-Max-ATSP with polynomial running time. Max-3-DCC is the following problem: Given an edgeweighted complete loopless directed graph, compute a spanning collection of node-disjoint cycles, each of length at least three, whose weight is maximum among all such collections. We present a 3/4-approximation algorithm for this problem with polynomial running time. In both cases, we improve on the previous best approximation performances. The results are obtained via a new decomposition technique for the fractional solution of an LP formulation of Max-3-DCC. © Springer-Verlag Berlin Heidelberg 2005.