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.
Citation
"Algorithmic Applications in Management: First International Conference, AAIM 2005, Xian, China, June 22-25, 2005." Editors: Nimrod Megiddo, Yinfeng Xu, Binhai Zhu. Lecture Notes in Computer Science, Springer (2005)pp.95-103. DOI: 10.1007/11496199_12