English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

The online list labeling problem is an algorithmic primitive with a largeliterature of upper bounds, lower bounds, and applications. The goal is tostore a dynamically-changing set of $n$ items in an array of $m$ slots, whilemaintaining the invariant that the items appear in sorted order, and whileminimizing the relabeling cost, defined to be the number of items that aremoved per insertion/deletion.  For the linear regime, where $m = (1 + \Theta(1)) n$, an upper bound of$O(\log^2 n)$ on the relabeling cost has been known since 1981. A lower boundof $\Omega(\log^2 n)$ is known for deterministic algorithms and for so-calledsmooth algorithms, but the best general lower bound remains $\Omega(\log n)$.The central open question in the field is whether $O(\log^2 n)$ is optimal forall algorithms.  In this paper, we give a randomized data structure that achieves an expectedrelabeling cost of $O(\log^{3/2} n)$ per operation. More generally, if $m = (1+ \varepsilon) n$ for $\varepsilon = O(1)$, the expected relabeling costbecomes $O(\varepsilon^{-1} \log^{3/2} n)$.  Our solution is history independent, meaning that the state of the datastructure is independent of the order in which items are inserted/deleted. Forhistory-independent data structures, we also prove a matching lower bound: forall $\epsilon$ between $1 / n^{1/3}$ and some sufficiently small positiveconstant, the optimal expected cost for history-independent list-labelingsolutions is $\Theta(\varepsilon^{-1}\log^{3/2} n)$.

Online List Labeling: Breaking the $\log^2n$ Barrier