Back to Search
Start Over
A linear-time algorithm to solve the Sports League Scheduling Problem (prob026 of CSPLib)
- Source :
-
Discrete Applied Mathematics . Sep2004, Vol. 143 Issue 1-3, p252-265. 14p. - Publication Year :
- 2004
-
Abstract
- In this paper, we present a repair-based linear-time algorithm to solve a version of the Sports League Scheduling Problem (SLSP) where the number <f>T</f> of teams is such that <f>(T-1) mod 3≠0</f>. Starting with a conflicting schedule with particular properties, the algorithm removes iteratively the conflicts by exchanging matches. The properties of the initial schedule make it possible to take the optimal exchange at each iteration, leading to a linear-time algorithm. This algorithm can find thus valid schedules for several thousands of teams in less than <f>1 min</f>. It is still an open question whether the SLSP can be solved efficiently when <f>(T-1) mod 3=0</f>. [Copyright &y& Elsevier]
- Subjects :
- *ALGORITHMS
*ALGEBRA
*MATHEMATICS
*MATHEMATICAL analysis
Subjects
Details
- Language :
- English
- ISSN :
- 0166218X
- Volume :
- 143
- Issue :
- 1-3
- Database :
- Academic Search Index
- Journal :
- Discrete Applied Mathematics
- Publication Type :
- Academic Journal
- Accession number :
- 14187890
- Full Text :
- https://doi.org/10.1016/j.dam.2003.10.009