.png){kind=icon}
.png){kind=icon}
Return
Improved Online Sorting
.png){kind=icon}
PRE
AI
DOI：10.1007/978-3-032-06706-7_13.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
We study the online sorting problem, where n real numbers arrive in an online fashion, and the algorithm must immediately place each number into an array of size (1 + e)n before seeing the next number. After all n numbers are placed into the array, the cost is defined as the sum over the absolute differences of all n - 1 pairs of adjacent numbers in the array, ignoring empty array cells. Aamand, Abrahamsen, Beretta, and Kleist introduced the problem and obtained a deterministic algorithm with cost 2O v log n center dot log log n+log e-1 , and a lower bound of O(log n/ log log n) for deterministic algorithms. We obtain a deterministic4 algorithm with quasi-polylogarithmic cost e- 1 log n O(log log n). Concurrent and independent work by Azar, Panigrahi, and Vardi achieves polylogarithmic cost O(e- 1 log2 n).
Keywords:
Online algorithms
Sorting
Data structures
Journal
A
IF:
0
Papers:
15
Citations:
0