Nearly Tight Bounds for the Online Sorting Problem
Preprint
Abstract
In the online sorting problem, a sequence of $n$ numbers in $[0, 1]$ (including $\{0,1\}$) have to be inserted in an array of size $m \ge n$ so as to minimize the sum of absolute differences between pairs of numbers occupying consecutive non-empty cells. Previously, Aamand {\em et al.} (SODA 2023) gave a deterministic $2^{\sqrt{\log n} \sqrt{\log \log n + \log (1/\varepsilon)}}$-competitive algorithm when $m = (1+\varepsilon) n$ for any $\varepsilon \ge Ω(\log n/n)$. They also showed a lower bound: with $m = γn$ space, the competitive ratio of any deterministic algorithm is at least $\frac{1}γ\cdotΩ(\log n / \log \log n)$. This left an exponential gap between the upper and lower bounds for the problem. In this paper, we bridge this exponential gap and almost completely resolve the online sorting problem. First, we give a deterministic $O(\log^2 n / \varepsilon)$-competitive algorithm with $m = (1+\varepsilon) n$, for any $\varepsilon \ge Ω(\log n / n)$. Next, for $m = γn$ where $γ= [O(1), O(\log^2 n)]$, we give a deterministic $O(\log^2 n / γ)$-competitive algorithm. In particular, this implies an $O(1)$-competitive algorithm with $O(n \log^2 n)$ space, which is within an $O(\log n\cdot \log \log n)$ factor of the lower bound of $Ω(n \log n / \log \log n)$. Combined, the two results imply a close to optimal tradeoff between space and competitive ratio for the entire range of interest: specifically, an upper bound of $O(\log^2 n)$ on the product of the competitive ratio and $γ$ while the lower bound on this product is $Ω(\log n / \log\log n)$. We also show that these results can be extended to the case when the range of the numbers is not known in advance, for an additional $O(\log n)$ factor in the competitive ratio.
Keywords
All Related Versions
This publication has 7 references indexed in Scilit:
- Nearly Optimal Bounds for Stochastic Online Sorting2026
- A note on online strip packingJournal of Combinatorial Optimization, 2008
- Shelf algorithms for on-line strip packingInformation Processing Letters, 1997
- Two-dimensional rectangle packing: on-line methods and resultsDiscrete Applied Mathematics, 1993
- An on-line algorithm for multidimensional bin packingOperations Research Letters, 1993
- Multidimensional on-line bin packing: Algorithms and worst-case analysisOperations Research Letters, 1989
- Shelf Algorithms for Two-Dimensional Packing ProblemsSIAM Journal on Computing, 1983