Semidefinite Programming Based Approaches to Home-Away Assignment Problems in Sports Scheduling.

For a given schedule of a round-robin tournament and a matrix of distances between homes of teams, an optimal home-away assignment problem is to find a home-away assignment that minimizes the total traveling distance. We propose a technique to transform the problem to MIN RES CUT . We apply Goemans and Williamson's 0.878-approximation algorithm for MAX RES CUT, which is based on a positive semidefinite programming relaxation,to the obtained MIN RES CUT instances. Computational experiments show that our approach quickly generates solutions of good approximation ratios. Keywords: Sports timetabling; semidefinite programming; Goemans and Williamson's approximation algorithm. [ABSTRACT FROM AUTHOR]