| Presentation | 2022-03-06 On properties of Kirkman schedules applied the partial team swap Yusuke Kashiwagi, |
|---|---|
| PDF Download Page |  PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | In this study, we show some properties of Kirkman schedules in applying the partial team swap. Kirkman schedule is the most representative single-round schedule in sports scheduling problems. The partial team swap (PTS) and the partial round swap (PRS) are representative neighborhood search methods in local search for sports scheduling problem. Let $n$ be the number of teams, $k$ be some team other than $n$, and $p$ be a prime number. Also, let $P_{i,j}= [n] verb|| { i,j }=bigcup_{x=1}^{X_{i,j}}{P_{i,j}^{x}}$, where $P_{i,j}^{x}$ is the set of vertices split by Partial Team Swap, and $X_{i,j}$ is the number of splits when $i,j$ are exchange points. We showed the property that a Kirkman schedule satisfying (1) $n-1 neq p$ or (2) $n-1=p and P^{x}_{k,n}subsetneq P_{k,n}$ can not be a Kirkman schedule when applied the partial team swap. The above property has already been shown in cite{riffle}, but the proofs of (1) and (2) were done using different lemmas, so we simplified the proofs and gave a unified proof using only one lemma for the two conditions. As a supplement, assuming that $n-1=p$, in the proposition that if $n-1$ is a Mersenne prime, then $P^{x}_{i,j}subsetneq [n]verb|| { i,j }$, the sufficient condition is satisfied but it is not necessary. We also showed that applying Partial Round Swap a Kirkman schedule can not be a Kirkman schedule isormorphic to the original one. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | Sports Scheduling Problem / Kirkman Schedule / Partial Team Swap / Partial Round Swap |
| Paper # | COMP2021-33 |
| Date of Issue | 2022-02-27 (COMP) |
| Conference Information | |
| Committee | COMP |
|---|---|
| Conference Date | 2022/3/6(1days) |
| Place (in Japanese) | (See Japanese page) |
| Place (in English) | Online |
| Topics (in Japanese) | (See Japanese page) |
| Topics (in English) | |
| Chair | Toshimitsu Masuzawa(Osaka Univ.) |
| Vice Chair | Hirotaka Ono(Nagoya Univ) |
| Secretary | Hirotaka Ono(NAIST) |
| Assistant | Yota Otachi(Nagoya Univ) |
| Paper Information | |
| Registration To | Technical Committee on Theoretical Foundations of Computing |
|---|---|
| Language | JPN |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | On properties of Kirkman schedules applied the partial team swap |
| Sub Title (in English) | |
| Keyword(1) | Sports Scheduling Problem |
| Keyword(2) | Kirkman Schedule |
| Keyword(3) | Partial Team Swap |
| Keyword(4) | Partial Round Swap |
| 1st Author's Name | Yusuke Kashiwagi |
| 1st Author's Affiliation | Seikei University(Seikei Univ) |
| Date | 2022-03-06 |
| Paper # | COMP2021-33 |
| Volume (vol) | vol.121 |
| Number (no) | COMP-407 |
| Page | pp.pp.16-23(COMP), |
| #Pages | 8 |
| Date of Issue | 2022-02-27 (COMP) |