Semidefinite Programming Based Approaches to Home-away Assignment Problems in Sports Scheduling
Ayami Suzuka (asuzukask.tsukuba.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
Modify/Update this entry
|Visitors||Authors||More about us||Links|
Search, Browse the Repository
Give us feedback
|Optimization Journals, Sites, Societies|