Single Approximation for Biobjective Max TSP

We propose an algorithm which returns a single Hamiltonian cycle with performance guarantee on both objectives. The algorithm is analysed in three cases. When both (resp. at least one) objective function(s) fulfill(s) the triangle inequality, the approximation ratio is 512−041 (resp. 83−). When the triangle inequality is not assumed on any objective function, the algorithm is 141+22−027 -approximate.ouinonouirechercheInternationa