It is proved that, for arbitrary $p and arbitrary initial orderings $\sigma$ and arbitrary initial orderings $\sigma$, after polynomially many queries in the number of items, the expected cost of a query is at most $\mathsf{OPT} + O(1)$.
Abstract
In the classical list update problem, a set of items must be stored in a list-type structure, where accessing the $i$-th element costs $i$. Items will be queried in an IID manner according to some probability distribution $p$ on the items. We want to minimize the expected cost of each query. The optimal order is to place the items in decreasing order of probability $p_1 \geq p_2 \geq \cdots$ with expected cost $\mathsf{OPT} = \sum_j j p_j$, but the probability vector $p$ is generally unknown. Thus we use a self-organizing list following the transposition rule: an item is transposed 1 position forward whenever it is queried. Coester (2026) proved that, at stationarity measure for the transposition rule, the expected cost of a query is at most $\mathsf{OPT} + 1$. However, this Markov chain may have arbitrarily slow mixing time. We prove that, for arbitrary $p$ and arbitrary initial orderings $\sigma$, after polynomially many queries in the number of items, the expected cost of a query is at most $\mathsf{OPT} + O(1)$.
We consider union-find with deletions, where the representation and the cost of a query must depend on the current number of live elements rather than on the number of elements ever created. For every integer parameter $k\ge 2$, we give a linear-space data structure supporting $\mathsf{MakeSet}$ in $O(1)$ worst-case ti...
The selection problem asks to find the $k$-th smallest element in a given set $X$. Its complexity is well-known to be $\Theta(|X|)$ for every fixed $k$. We consider the poset selection problem where a partial order $P$ on $X$ is given, and the underlying order of $X$ is guaranteed to be a linear extension of $P$. This...
This paper gives a precise characterization of when the ambient address space yields a genuine quantum advantage for linked-list search, and extends the results and gives the same tight asymptotic bounds for the natural double linked-list version as well.
The ordinal algorithm accepts every element of a fixed canonical optimum with probability exactly $1/C_*$ and uses O(n^2)$ independence queries and the resulting guarantee has a direct analytic proof.
Hau Chan, Jia-Nan Lin, Chen-Hao Wang· arXiv.org· 5 citations· ⚡2
The proof extends adaptive Wishart deferred decisions to a rectangular factor with a $k$-dimensional nullspace while persistence of small compression eigenvalues controls growing $p$ and the spectral endpoint.
A dictionary is a data structure which stores pairs (key, value). The operation query on input key returns value if the dictionary contains a pair (key, value) and nil otherwise. A dynamic dictionary also supports the insert and delete operations. The model with cells of bitsize $n + m + 1$ is used, where $n$ and $m$ a...
Bruno Bauwens, Marius Zimand· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.