Optimization Online


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

Ayami Suzuka (asuzuka***at***sk.tsukuba.ac.jp)
Ryuhei Miyashiro (r-miya***at***cc.tuat.ac.jp)
Akiko Yoshise (yoshise***at***sk.tsukuba.ac.jp)
Tomomi Matsui (tomomi***at***misojiro.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


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

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society