IEICE TRANSACTIONS on Information
Efficient Algorithms for Sorting k-Sets in Bins
Summary :
We propose efficient algorithms for Sorting k-Sets in Bins. The Sorting k-Sets in Bins problem can be described as follows. We are given numbered n bins with k balls in each bin. Balls in the i-th bin are numbered n-i+1. We can only swap balls between adjacent bins. Our task is to move all of the balls to the same numbered bins. For this problem, we give an efficient greedy algorithm with $ rac{k+1}{4}n^2+O(k+n)$ swaps and provide a detailed analysis for k=3. In addition, we give a more efficient recursive algorithm using $ rac{15}{16}n^2+O(n)$ swaps for k=3.
- Publication
- IEICE TRANSACTIONS on Information Vol.E98-D No.10 pp.1736-1743
- Publication Date
- 2015/10/01
- Publicized
- Online ISSN
- 1745-1361
- DOI
- 10.1587/transinf.2015EDP7038
- Type of Manuscript
- PAPER
- Category
- Fundamentals of Information Systems
Authors
Atsuki NAGAO
Kyoto University,Research Fellow of Japan Society for the Promotion of Science
Kazuhisa SETO
Seikei University
Junichi TERUYAMA
National Institute of Informatics,JST, ERATO, Kawarabayashi Large Graph Project
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Atsuki NAGAO, Kazuhisa SETO, Junichi TERUYAMA, "Efficient Algorithms for Sorting k-Sets in Bins" in IEICE TRANSACTIONS on Information,
vol. E98-D, no. 10, pp. 1736-1743, October 2015, doi: 10.1587/transinf.2015EDP7038.
Abstract: We propose efficient algorithms for Sorting k-Sets in Bins. The Sorting k-Sets in Bins problem can be described as follows. We are given numbered n bins with k balls in each bin. Balls in the i-th bin are numbered n-i+1. We can only swap balls between adjacent bins. Our task is to move all of the balls to the same numbered bins. For this problem, we give an efficient greedy algorithm with $ rac{k+1}{4}n^2+O(k+n)$ swaps and provide a detailed analysis for k=3. In addition, we give a more efficient recursive algorithm using $ rac{15}{16}n^2+O(n)$ swaps for k=3.
URL: https://global.ieice.org/en_transactions/information/10.1587/transinf.2015EDP7038/_p
Copy
@ARTICLE{e98-d_10_1736,
author={Atsuki NAGAO, Kazuhisa SETO, Junichi TERUYAMA, },
journal={IEICE TRANSACTIONS on Information},
title={Efficient Algorithms for Sorting k-Sets in Bins},
year={2015},
volume={E98-D},
number={10},
pages={1736-1743},
abstract={We propose efficient algorithms for Sorting k-Sets in Bins. The Sorting k-Sets in Bins problem can be described as follows. We are given numbered n bins with k balls in each bin. Balls in the i-th bin are numbered n-i+1. We can only swap balls between adjacent bins. Our task is to move all of the balls to the same numbered bins. For this problem, we give an efficient greedy algorithm with $ rac{k+1}{4}n^2+O(k+n)$ swaps and provide a detailed analysis for k=3. In addition, we give a more efficient recursive algorithm using $ rac{15}{16}n^2+O(n)$ swaps for k=3.},
keywords={},
doi={10.1587/transinf.2015EDP7038},
ISSN={1745-1361},
month={October},}
Copy
TY - JOUR
TI - Efficient Algorithms for Sorting k-Sets in Bins
T2 - IEICE TRANSACTIONS on Information
SP - 1736
EP - 1743
AU - Atsuki NAGAO
AU - Kazuhisa SETO
AU - Junichi TERUYAMA
PY - 2015
DO - 10.1587/transinf.2015EDP7038
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E98-D
IS - 10
JA - IEICE TRANSACTIONS on Information
Y1 - October 2015
AB - We propose efficient algorithms for Sorting k-Sets in Bins. The Sorting k-Sets in Bins problem can be described as follows. We are given numbered n bins with k balls in each bin. Balls in the i-th bin are numbered n-i+1. We can only swap balls between adjacent bins. Our task is to move all of the balls to the same numbered bins. For this problem, we give an efficient greedy algorithm with $ rac{k+1}{4}n^2+O(k+n)$ swaps and provide a detailed analysis for k=3. In addition, we give a more efficient recursive algorithm using $ rac{15}{16}n^2+O(n)$ swaps for k=3.
ER -
English
