| Selection from read-only memory with limited workspace | |
| Authors: | Amr Elmasry, Daniel Dahl Juhl, Jyrki Katajainen, and Srinivasa Rao Satti |
| Published in: | Proceedings of the 19th Annual International Computing and Combinatorics Conference, Lecture Notes in Computer Science 7936, Springer-Verlag (2013), 147-157 |
| Full text: |  PDF (170 kB) |
| DOI: | 10.1007/978-3-642-38768-5_15 |
| Copyright: | © Springer-Verlag GmbH Berlin Heidelberg |
| Abstract: | In the classic selection problem the task is to find the kth smallest of N elements. We study the complexity of this problem on a space-bounded random-access machine: The input is given in a read-only array and the capacity of workspace is limited. We prove that the linear-time prune-and-search algorithm—presented in most textbooks on algorithms—can be adjusted to use O(N) bits instead of Θ(N) words of extra space. Prior to our work, the best known algorithm by Frederickson could perform the task with O(N) bits of extra space in O(N log* N) time. In particular, our result separates the space-restricted random-access model and the multi-pass streaming model (since we can bypass the Ω(N log* N) lower bound known for the latter model). We also generalize our algorithm for the case when the size of the workspace is O(S) bits, lg3N ≤ S ≤ N. The running time of our generalized algorithm is O(N lg*(N/S) + N lg N / lg S), slightly improving over the bound O(N lg*(N lg N/S) + N lg N / lg S) of Frederickson’s algorithm. Of independent interest, the wavelet stack—a structure we used for repeated pruning—may also be useful in other applications. |
| Related: |  HTML (Journal article) HTML (Extended version) HTML (Errata) |
| BibLATEX: | @inproceedings{EJKS2013C,
author = {Amr Elmasry and Daniel Dahl Juhl and Jyrki Katajainen and Srinivasa
Rao Satti},
title = {Selection from read-only memory with limited workspace},
booktitle = {Proceedings of the 19th Annual International Computing and
Combinatorics Conference},
series = {Lecture Notes in Computer Science},
volume = {7936},
publisher = {Springer-Verlag},
year = {2013},
pages = {147--157},
}
|