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

Ayami Suzuka (asuzukask.tsukuba.ac.jp)
Ryuhei Miyashiro (r-miyacc.tuat.ac.jp)
Akiko Yoshise (yoshisesk.tsukuba.ac.jp)
Tomomi Matsui (tomomimisojiro.t.u-tokyo.ac.jp)

Abstract: 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.

Category 1: Combinatorial Optimization (Approximation Algorithms )

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

Download:

Entry Submitted: 03/03/2005
Entry Accepted: 03/03/2005
Entry Last Modified: 05/30/2005

Modify/Update this entry