An Approximation Algorithm for the Bipartite Traveling Tournament Problem

作者：Hoshino Richard^*; Kawarabayashi Ken ichi

来源：Mathematics of Operations Research, 2013, 38(4): 720-728.

DOI：10.1287/moor.2013.0597

• scheduling
• approximation algorithms
• traveling tournament problem
• traveling salesman

The bipartite traveling tournament problem (BTTP) is an NP-complete scheduling problem whose solution is a double round-robin inter-league tournament with minimum total travel distance. The 2n-team BTTP is a variant of the well-known traveling salesman problem (TSP), albeit much harder as it involves the simultaneous coordination of 2n teams playing a sequence of home and away games under fixed constraints, rather than a single entity passing through the locations corresponding to the teams' home venues. As the BTTP requires a distance-optimal schedule linking venues in close proximity, we provide an approximation algorithm for the BTTP based on an approximate solution to the corresponding TSP.
We prove that our polynomial-time algorithm generates a 2n-team inter-league tournament schedule whose total distance is at most 1 + 2c/3 + (3 c)/(3n) times the total distance of the optimal BTTP solution, where c is the approximation factor of the TSP. In practice, the actual approximation factor is far better; we provide a specific example by generating a nearly-optimal inter-league tournament for the 30-team National Basketball Association, with total travel distance just 1.06 times the trivial theoretical lower bound.

• 出版日期2013-11