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.
展开▼
机译：对于给定的循环赛赛程和球队两队之间的距离矩阵，最佳的离家出走分配问题是找到使总行驶距离最小的离家出走分配。我们提出了一种将问题转换为MIN RES CUT的技术。对于获得的MIN RES CUT实例，我们将基于正半定程序松弛的Goemans和Williamson的0.878近似算法用于MAX RES CUT。计算实验表明，我们的方法可以快速生成具有良好近似率的解。
展开▼
