Semidefinite Programming Based Approaches to Home-Away Assignment Problems in Sports Scheduling | Zendy

Ayami Suzuka | Zendy; Ryuhei Miyashiro | Zendy; Akiko Yoshise | Zendy; Tomomi Matsui | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

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

Author(s) -

Ayami Suzuka,

Ryuhei Miyashiro,

Akiko Yoshise,

Tomomi Matsui

Publication year - 2005

Publication title -

lecture notes in computer science

Language(s) - English

Resource type - Book series

SCImago Journal Rank - 0.249

H-Index - 400

eISSN - 1611-3349

pISSN - 0302-9743

ISBN - 3-540-26224-5

DOI - 10.1007/11496199_12

Subject(s) - semidefinite programming , scheduling (production processes) , relaxation (psychology) , tournament , computer science , schedule , mathematical optimization , linear programming relaxation , matrix (chemical analysis) , linear programming , algorithm , combinatorics , mathematics , psychology , social psychology , materials science , composite material , operating system

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.

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research