Multicolor traveling salesman problem: approximation and feasibility

Frédéric Meunier (1) , Pauline Sarrabezolles (1)

1 CERMICS - Centre d'Enseignement et de Recherche en Mathématiques et Calcul Scientifique

The multicolor traveling salesman problem (MTSP) is defined on a complete graph whose vertex set is partitioned into $k$ subsets, identified with colors. It aims to find a shortest Hamiltonian tour subject to restrictions: the number of vertices of the subtour between two consecutive vertices of the same color is bounded from above and from below. In this work, we propose new approximation algorithms. Some special cases with two colors have already received attention: the bipartite traveling salesman problem and the black-and-white traveling salesman problem. Polynomial-time approximation algorithms are known for these problems. We cover new cases with two colors and a special case when all colors have same size. In addition, we find necessary conditions and sufficient conditions for the MTSP to have feasible solutions. Finally, we establish a connection between the balance properties of words and the existence of feasible solutions for the MTSP.

Mots clés: approximation algorithms; balance properties of words; black-and-white traveling salesman problem; traveling salesman problem

Domaines: Mathématique discrète [cs.DM]

Frédéric Meunier, Pauline Sarrabezolles. Multicolor traveling salesman problem: approximation and feasibility. 2013. ⟨hal-00863493⟩