Art

J-GLOBAL ID：201702289513485064   Reference number：17A0539062

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

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

Author (3)： SHIMIZU KENTO (成蹊大) ,  MITSUHASHI TATSUYA (成蹊大) ,  SETO KAZUHISA (成蹊大)
Material： 電子情報通信学会技術研究報告  (IEICE Technical Report (Institute of Electronics, Information and Communication Engineers))
Volume： 116  Issue： 503(COMP2016 50-55)  Page： 29-32  Publication year： Feb. 28, 2017 
JST Material Number： S0532B  ISSN： 0913-5685  Document type： Proceedings
Article type： 原著論文  Country of issue： Japan (JPN)  Language： JAPANESE (JA)

Thesaurus term： *sorting (computer) ,  *computer algorithm ,  *maximum problem ,  exchange ,  *bin packing problem ,  theorem ,  set ,  analysis ,  program theory ,  computational complexity ,  recursive algorithm ,  algorithm analysis
Semi thesaurus term： sorting ,  greedy method

JST classification (2)： Theory of computation  (JB02000A) ,  Other methods of operations research  (KA03070E)

Reference (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.

Terms in the title (2)： 貪欲アルゴリズム ,  上界