Semidefinite programming based approaches to the break minimization problem

摘要

This paper considers the break minimization problem in sports timetabling. The problem is to find, under a given timetable of a round-robin tournament, a home-away assignment that minimizes the number of breaks, i.e., the number of occurrences of consecutive matches held either both at away or both at home for a team. We formulate the break minimization problem as MAX RES CUT and MAX 2SAT, and apply Goemans and Williamson's approximation algorithm using semidefinite programming. Computational experiments show that our approach quickly generates solutions of good approximation ratios.