WEKO3
アイテム
輪番割当問題の密度限界と最頻周期
https://ipsj.ixsq.nii.ac.jp/records/241902
https://ipsj.ixsq.nii.ac.jp/records/241902561806c7-0bf2-457e-a5c6-fcaf035d1fdc
| 名前 / ファイル | ライセンス | アクション |
|---|---|---|
IPSJ-AL25201014.pdf (882.7 kB)
2027年1月7日からダウンロード可能です。
|
Copyright (c) 2025 by the Information Processing Society of Japan
|
|
| 非会員：¥660, IPSJ:学会員：¥330, AL:会員：¥0, DLIB:会員：¥0 | ||
| Item type | SIG Technical Reports(1) | |||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 公開日 | 2025-01-07 | |||||||||||
| タイトル | ||||||||||||
| タイトル | 輪番割当問題の密度限界と最頻周期 | |||||||||||
| 言語 | ||||||||||||
| 言語 | jpn | |||||||||||
| 資源タイプ | ||||||||||||
| 資源タイプ識別子 | http://purl.org/coar/resource_type/c_18gh | |||||||||||
| 資源タイプ | technical report | |||||||||||
| 著者所属 | ||||||||||||
| 京都大学 | ||||||||||||
| 著者所属 | ||||||||||||
| 京都大学 | ||||||||||||
| 著者所属 | ||||||||||||
| 京都大学 | ||||||||||||
| 著者名 |
河村, 彰星
× 河村, 彰星
× 草野, 陽介
× 小林, 佑輔
|
|||||||||||
| 論文抄録 | ||||||||||||
| 内容記述タイプ | Other | |||||||||||
| 内容記述 | いくつかの仕事を一日に一つずつ行うという状況を考える．輪番割当問題とは，各仕事に定められた頻度条件「連続する○○日に一度以上行わなければならない」という制約を満たしながら仕事を無限に続けられるかを問うものである．この「○○」にあたるものをその仕事の周期といい，これまで輪番割当問題では，密度と呼ばれる各周期の逆数の総和と，条件を満たす仕事の割当可能性との関係性について研究されてきた．例えば，密度 1/2 以下であるような周期の組は，必ず割当可能であることが知られている．この 1/2 のような，割当可能性に対する密度の十分条件を密度限界と呼ぶ．我々は，最も小さい周期すなわち最頻周期が十分大きい場合の密度限界を，周期の実数拡張を考えることで改善した． | |||||||||||
| 書誌レコードID | ||||||||||||
| 収録物識別子タイプ | NCID | |||||||||||
| 収録物識別子 | AN1009593X | |||||||||||
| 書誌情報 |
研究報告アルゴリズム（AL） 巻 2025-AL-201, 号 14, p. 1-3, 発行日 2025-01-07 |
|||||||||||
| ISSN | ||||||||||||
| 収録物識別子タイプ | ISSN | |||||||||||
| 収録物識別子 | 2188-8566 | |||||||||||
| Notice | ||||||||||||
| SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc. | ||||||||||||
| 出版者 | ||||||||||||
| 言語 | ja | |||||||||||
| 出版者 | 情報処理学会 | |||||||||||
