An Approximation Algorithm for the Bipartite Traveling Tournament Problem

• Published in: Mathematics of operations research 2013-11, Vol.38 (4), p.720-728
• Main Authors: Hoshino, Richard, Kawarabayashi, Ken-ichi
• Format: Article
• Language: English
• Subjects: Algorithms; approximation algorithms; Approximations; Management science; Optimization algorithms; Polynomials; scheduling; Scheduling algorithms; Studies; Teams; traveling salesman; Traveling salesman problem; traveling tournament problem
• ISSN: 0364-765X; 1526-5471
• DOI: 10.1287/moor.2013.0597

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 2 n -team BTTP is a variant of the well-known traveling salesman problem (TSP), albeit much harder as it involves the simultaneous coordination of 2 n 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 2 n -team inter-league tournament schedule whose total distance is at most 1 + 2 c /3 + (3 − c )/(3 n ) 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.