講演抄録/キーワード |
講演名 |
2017-03-07 15:20
Sorting k-Sets in Bins問題に対する貪欲アルゴリズムの上界の改良 清水堅斗・三觜辰也・○脊戸和寿(成蹊大) COMP2016-55 |
抄録 |
(和) |
本研究ではSorting $k$-Sets in Bins問題に対する貪欲アルゴリズムの理論的解析を行う.
Sorting $k$-Sets in Bins問題とは,各ビンに$k$個の同じ番号のボールが入った$n$個のビンが与えられる.
ここで,$i (leq i leq n)$番目のビン内にあるボールは$n-i+1$の番号をもつボールが入っているものとする.
このとき,隣合うビン内の2つのボールを交換する操作によって,$i$番目のビンには番号$i$の全てのボールが入るように整列を行う.
この問題に対し,2015年にNagao, Seto, Teruyamaによって,$frac{k+1}{4}n^2+O(k+n)$の交換回数で整列できる貪欲アルゴリズムが示されている.
また,彼らは$k=3$の場合に貪欲アルゴリズムは$frac{24}{25}n^2+O(n)$で整列を行うことを示している.
本研究では,この解析を一般の$k$に拡張することで,貪欲アルゴリズムが$frac{k^3+5k^2+6k+6}{4(k+2)^2}{n}^{2}+O(n)$回の交換回数で
Sorting $k$-Sets in Bins問題を解くことを示した. |
(英) |
(Not available yet) |
キーワード |
(和) |
ソート / 貪欲アルゴリズム / / / / / / |
(英) |
/ / / / / / / |
文献情報 |
信学技報, vol. 116, no. 503, COMP2016-55, pp. 29-32, 2017年3月. |
資料番号 |
COMP2016-55 |
発行日 |
2017-02-28 (COMP) |
ISSN |
Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 |
著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します.(許諾番号:10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) |
PDFダウンロード |
COMP2016-55 |