Scheduling Algorithms for new Emerging Applications

May, 29th - June, 2nd 2006, CIRM, Marseille, France

Round robin tournaments and three index assignment

SpeakerDirk Briskorn

Co-authorsAndreas Drexl and Frits C. R. Spieksma

In general scheduling a sports league is a difficult combinatorial optimization problem. We study some variants of round robin tournaments and analyze the relationship to the planar three index assignment problem. The complexity of round robin tournaments is proven by reduction from the planar three index assignment problem.

Furthermore, integer programming models are introduced. We pick up a popular idea and decompose the overall problem in order to obtain two subproblems which can be solved sequentially. The latter subproblem can be represented as planar three index assignment problem which makes corresponding solution techniques amenable to sports league scheduling.