文献

J-GLOBAL ID：201702289513485064   整理番号：17A0539062

Sorting k-Sets in Bins問題に対する貪欲アルゴリズムの上界の改良

Improved Analysis of Greedy Algorithm for Sorting k-Sets in Bins

著者 (3件)： 清水堅斗 (成蹊大) ,  三觜辰也 (成蹊大) ,  脊戸和寿 (成蹊大)
資料名： 電子情報通信学会技術研究報告  (IEICE Technical Report (Institute of Electronics, Information and Communication Engineers))
巻： 116  号： 503(COMP2016 50-55)  ページ： 29-32  発行年： 2017年02月28日 
JST資料番号： S0532B  ISSN： 0913-5685  資料種別： 会議録 (C)
記事区分： 原著論文  発行国： 日本 (JPN)  言語： 日本語 (JA)

抄録/ポイント： 本研究ではSorting k-Sets in Bins問題に対する貪欲アルゴリズムの理論的解析を行う。Sorting k-Sets in Bins問題とは,各ビンにk個の同じ番号のボールが入ったn個のビンが与えられる。ここで,i(≦i≦n)番目のビン内にあるボールはn-i+1の番号をもつボールが入っているものとする。このとき,隣合うビン内の2つのボールを交換する操作によって,i番目のビンには番号iの全てのボールが入るように整列を行う。この問題に対し,2015年にNagao,Seto,Teruyamaによって,(k+1)/4 n²+O(k+n)の交換回数で整列できる貪欲アルゴリズムが示されている。また,彼らはk=3の場合に貪欲アルゴリズムは24/25 n²+O(n)で整列を行うことを示している。本研究では,この解析を一般のkに拡張することで,貪欲アルゴリズムが(k³+5k²6k+6)/(4(k+2)²) n²+O(n)回の交換回数でSorting k-Sets in Bins問題を解くことを示した。(著者抄録)

シソーラス用語： *ソーティング ,  *計算機アルゴリズム ,  *最大化問題 ,  交換 ,  *ビンパッキング問題 ,  定理 ,  集合 ,  解析 ,  プログラム理論 ,  計算量
準シソーラス用語： ソート ,  貪欲法 ,  再帰アルゴリズム ,  アルゴリズム解析

分類 (2件)： 計算理論  (JB02000A) ,  その他のオペレーションズリサーチの手法  (KA03070E)

引用文献 (13件)：

• D. Cranston, I. H. Sudborough, and D. B. West: Short Proofs for Cut-and-Paste Sorting of Permutations. Discrete Mathematics 307, pp.2866-2870, 2007.
• C. Daskalakis, R. M. Karp, E. Mossel, S. J. Eiesenfeld, and E. Verbin: Sorting and selection in posets. SIAM Journal on Computing, 40(3): pp.597-622, 2011.
• H. Dweighter: Elementary Problems. American Mathematical Monthly 82, 1010, 1975.
• S. Elizalde and P. Winkler: Sorting by Placement and Shift. Proc. ACM/SIAM Symp. on Discrete Algorithms (SODA), pp.68-75, 2009.
• H. Eriksson, K. Eriksson, J. Karlander, L. Svensson and J. W?stlund: Sorting a bridge hand. Discrete Math, 241,pp.289-300, 2001.

タイトルに関連する用語 (2件)： 貪欲アルゴリズム ,  上界