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

We consider online algorithms for the $k$-server problem on trees. Chrobakand Larmore proposed a $k$-competitive algorithm for this problem that has theoptimal competitive ratio. However, a naive implementation of their algorithmhas $O(n)$ time complexity for processing each query, where $n$ is the numberof nodes in the tree. We propose a new time-efficient implementation of thisalgorithm that has $O(n\log n)$ time complexity for preprocessing and$O\left(k^2 + k\cdot \log n\right)$ time for processing a query. We alsopropose a quantum algorithm for the case where the nodes of the tree arepresented using string paths. In this case, no preprocessing is needed, and thetime complexity for each query is $O(k^2\sqrt{n}\log n)$. When the number ofqueries is $o\left(\frac{\sqrt{n}}{k^2\log n}\right)$, we obtain a quantumspeed-up on the total runtime compared to our classical algorithm.  We also give a simple quantum algorithm to find the first marked element in acollection of $m$ objects, that works even in the presence of two-sided boundederrors on the input oracle. It has worst-case complexity $O(\sqrt{m})$. In theparticular case of one-sided errors on the input, it has expected timecomplexity $O(\sqrt{x})$ where $x$ is the position of the first marked element.Compare with previous work, our algorithm can handle errors in the inputoracle.

Fast Classical and Quantum Algorithms for Online $k$-server Problem on Trees