FRIDAY, October 17, 2003
Time: 2:00 - 3:00 PM
Constant Hall Room 1043

Dr. J. Mark Dorrepaal, Chairman
Department of Mathematics and Statistics
Old Dominion University

The n-team Traveling Tournament Problem (TTP) is a kind of nth order Traveling Salesman Problem which is of interest to Major League Baseball in the assembly of their team schedules. The definition of the problem with its various constraints and optimization objective can be found at the website http://mat.gsia.cmu.edu/TOURN/.

This talk attempts to quantify the total number of legal schedules S(n) as a function of the number of teams in the problem. The search for optimal solutions is necessarily computational and the magnitude of S(n) gives a measure of the staggering complexity of the problem for n>8. Analytical tools are discussed which help predict S(n) for n=10, 12, 14 and 16, the cases of interest at the website.