A TSP-Based Algorithm for Multi-League Traveling Tournament

Abstract

In some professional sports leagues, inter-league games are scheduled among multiple divisions or conferences. This inspired us to study the p-partite Traveling Tournament Problem (p-partite TTP), where teams are partitioned into p leagues, and each team plays games against teams from different leagues. Previously, only the case of p=2, known as the Bipartite TTP or BTTP, has been introduced and studied. In this paper, we show that the p-partite TTP is NP-hard for any fixed p≥3, and we propose an efficient algorithm based on a solution to the Traveling Salesman Problem. Furthermore, we prove that the algorithm achieves a notable approximation ratio of 8/3+O(1/n) when p=3. We also conduct experiments demonstrating that the algorithm produces practical schedules with significantly reduced total travel distances, highlighting its effectiveness in generating high-quality multipartite tournament schedules.