A sorted array is a fundamental algorithmic concept. Its on-line variant gives rise to the online labeling problem. In the online labeling problem we are given an array of size m and a stream of n integers from the universe {1, ..., r} coming in an arbitrary order. Our task is to maintain all received items in the array in sorted order. The inserted items do not have to be stored consecutively in the array. Since the final order of the items is not known until we see all the items, moves of already inserted items are allowed but should be minimized. We present two algorithms which together provide an optimal solution for almost all values of m as a function of n. We provide tight lower bounds for almost all ranges of m. We introduce a notion of the limited universe and prove lower bounds also in that setting. Some of our lower bounds also apply to randomized algorithms. Powered by TCPDF (www.tcpdf.org)
| Identifer | oai:union.ndltd.org:nusl.cz/oai:invenio.nusl.cz:332549 |
| Date | January 2014 |
| Creators | Bulánek, Jan |
| Contributors | Koucký, Michal, Brodal, Gerth, Iacono, John |
| Source Sets | Czech ETDs |
| Language | English |
| Detected Language | English |
| Type | info:eu-repo/semantics/doctoralThesis |
| Rights | info:eu-repo/semantics/restrictedAccess |
Page generated in 0.0018 seconds