| 講演名 | 2022-03-06 Partial Team Swapを適用したときのKirkmanスケジュールの特性について 柏木 佑介(成蹊大), |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | 本研究では，Partial Team Swapを適用したときのKirkmanスケジュールの特性について示す．Kirkmanスケジュールは，スポーツスケジューリング問題において最も代表的なシングルラウンドスケジュールである．Partial Team Swap（PTS）とPartial Round Swap（PRS）は，スポーツスケジューリングの局所探索において代表的な近傍探索である．$n$をチーム数，$k$を$n$以外のあるチームとし，$p$を素数とする．また，$P_{i,j}= [n] verb|| { i,j }=bigcup_{x=1}^{X_{i,j}}{P_{i,j}^{x}}$とする．ただし、それぞれの$P_{i,j}^{x}$は，Partial Team Swapの動作によって分割される頂点の集合であり，$X_{i,j}$は交換点$i,j$としたときの分割数を表している．(1)$n-1 neq p$，または(2)$n-1=p かつ P^{x}_{k,n}subsetneq P_{k,n}$を満たすKirkmanスケジュールが与えられたとき，Partial Team Swapを適用するとKirkmanスケジュールでなくなるという特性を示した．上記の証明は既にcite{riffle}で行われているが，(1)の証明と(2)の証明をそれぞれ別の補題を用いてなされていたため，証明の単純化を図り，2つの条件を1つの補題のみを用いて統一的な証明を与えた．補足として，[n-1がメルセンヌ素数であるLongrightarrow P^{x}_{i,j}subsetneq [n]verb|| { i,j }] となる命題において，十分条件は満たしているが必要条件は満たしていないことを示した．また，KirkmanスケジュールにPartial Round Swapを適用すると同型でないKirkmanスケジュールを生成できることも示した． |
| 抄録(英) | 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. |
| キーワード(和) | スポーツスケジューリング問題 / Kirkmanスケジュール / Partial Team Swap / Partial Round Swap |
| キーワード(英) | Sports Scheduling Problem / Kirkman Schedule / Partial Team Swap / Partial Round Swap |
| 資料番号 | COMP2021-33 |
| 発行日 | 2022-02-27 (COMP) |
| 研究会情報 | |
| 研究会 | COMP |
|---|---|
| 開催期間 | 2022/3/6(から1日開催) |
| 開催地（和） | オンライン開催 |
| 開催地（英） | Online |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | 増澤 利光(阪大) |
| 委員長氏名（英） | Toshimitsu Masuzawa(Osaka Univ.) |
| 副委員長氏名（和） | 小野 廣隆(名大) |
| 副委員長氏名（英） | Hirotaka Ono(Nagoya Univ) |
| 幹事氏名（和） | 大下 福仁(奈良先端大) / 安藤 映(専修大) |
| 幹事氏名（英） | Fukuhito Ooshita(NAIST) / Ei Ando(Senshu Univ.) |
| 幹事補佐氏名（和） | 大舘 陽太(名大) |
| 幹事補佐氏名（英） | Yota Otachi(Nagoya Univ) |
| 講演論文情報詳細 | |
| 申込み研究会 | Technical Committee on Theoretical Foundations of Computing |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | Partial Team Swapを適用したときのKirkmanスケジュールの特性について |
| サブタイトル（和） | |
| タイトル（英） | On properties of Kirkman schedules applied the partial team swap |
| サブタイトル（和） | |
| キーワード(1)（和/英） | スポーツスケジューリング問題 / Sports Scheduling Problem |
| キーワード(2)（和/英） | Kirkmanスケジュール / Kirkman Schedule |
| キーワード(3)（和/英） | Partial Team Swap / Partial Team Swap |
| キーワード(4)（和/英） | Partial Round Swap / Partial Round Swap |
| 第 1 著者 氏名（和/英） | 柏木 佑介 / Yusuke Kashiwagi |
| 第 1 著者 所属（和/英） | 成蹊大学(略称：成蹊大) Seikei University(略称：Seikei Univ) |
| 発表年月日 | 2022-03-06 |
| 資料番号 | COMP2021-33 |
| 巻番号（vol） | vol.121 |
| 号番号（no） | COMP-407 |
| ページ範囲 | pp.16-23(COMP), |
| ページ数 | 8 |
| 発行日 | 2022-02-27 (COMP) |