Efficient Algorithms for Sorting k-Sets in Bins
| Autor: | Junichi Teruyama, Kazuhisa Seto, Atsuki Nagao |
|---|---|
| Rok vydání: | 2015 |
| Předmět: |
Efficient algorithm
Sorting Upper and lower bounds Bin Combinatorics Artificial Intelligence Hardware and Architecture TheoryofComputation_ANALYSISOFALGORITHMSANDPROBLEMCOMPLEXITY Computer Vision and Pattern Recognition Electrical and Electronic Engineering Greedy algorithm Software MathematicsofComputing_DISCRETEMATHEMATICS Mathematics |
| Zdroj: | IEICE Transactions on Information and Systems. :1736-1743 |
| ISSN: | 1745-1361 0916-8532 |
| DOI: | 10.1587/transinf.2015edp7038 |
| Popis: | We give 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. How many swaps are needed to move all balls to the same numbered bins. For this problem, we design an efficient greedy algorithm with \(\frac{k+1}{4}n^2+O(kn)\) swaps. As k and n increase, this approaches the lower bound of \(\lceil \binom{kn}{2}/(2k-1) \rceil\). In addition, we design a more efficient recursive algorithm using \(\frac{15}{16}n^2+O(n)\) swaps for the k = 3 case. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|