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

We consider an APX-hard variant (Δ-Max-ATSP) and an APX-hard relaxation (Max-3-DCC) of the classical traveling salesman problem. We present a $\frac{31}{40}$ -approximation algorithm for Δ-Max-ATSP and a $\frac{3}{4}$ -approximation algorithm for Max-3-DCC with polynomial running time. The results are obtained via a new way of applying techniques for computing undirected cycle covers to directed problems.