Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | https://arxiv.org/abs/2508.14361 |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866908495616409600 |
|---|---|
| author | Nirjhor, Jubayer Wein, Nicole |
| author_facet | Nirjhor, Jubayer Wein, Nicole |
| contents | 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+\varepsilon) 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 $2^{O\left(\sqrt{\log n \cdot\log\log n +\log \varepsilon^{-1}}\right)}$, and a lower bound of $Ω(\log n / \log\log n)$ for deterministic algorithms. We obtain a deterministic algorithm with quasi-polylogarithmic cost $\left(\varepsilon^{-1}\log n\right)^{O\left(\log \log n\right)}$.
Concurrent and independent work by Azar, Panigrahi, and Vardi achieves polylogarithmic cost $O(\varepsilon^{-1}\log^2 n)$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2508_14361 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Improved Online Sorting Nirjhor, Jubayer Wein, Nicole Data Structures and Algorithms 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+\varepsilon) 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 $2^{O\left(\sqrt{\log n \cdot\log\log n +\log \varepsilon^{-1}}\right)}$, and a lower bound of $Ω(\log n / \log\log n)$ for deterministic algorithms. We obtain a deterministic algorithm with quasi-polylogarithmic cost $\left(\varepsilon^{-1}\log n\right)^{O\left(\log \log n\right)}$. Concurrent and independent work by Azar, Panigrahi, and Vardi achieves polylogarithmic cost $O(\varepsilon^{-1}\log^2 n)$. |
| title | Improved Online Sorting |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2508.14361 |