  In many professional sports leagues, teams from opposing leagues/conferences
compete against one another, playing inter-league games. This is an example of
a bipartite tournament. In this paper, we consider the problem of reducing the
total travel distance of bipartite tournaments, by analyzing inter-league
scheduling from the perspective of discrete optimization. This research has
natural applications to sports scheduling, especially for leagues such as the
National Basketball Association (NBA) where teams must travel long distances
across North America to play all their games, thus consuming much time, money,
and greenhouse gas emissions. We introduce the Bipartite Traveling Tournament
Problem (BTTP), the inter-league variant of the well-studied Traveling
Tournament Problem. We prove that the 2n-team BTTP is NP-complete, but for
small values of n, a distance-optimal inter-league schedule can be generated
from an algorithm based on minimum-weight 4-cycle-covers. We apply our
theoretical results to the 12-team Nippon Professional Baseball (NPB) league in
Japan, producing a provably-optimal schedule requiring 42950 kilometres of
total team travel, a 16% reduction compared to the actual distance traveled by
these teams during the 2010 NPB season. We also develop a nearly-optimal
inter-league tournament for the 30-team NBA league, just 3.8% higher than the
trivial theoretical lower bound.
