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

In STOC'16, Fraigniaud et al. consider the problem of finding a treasurehidden in one of many boxes that are ordered by importance. That is, if atreasure is in a more important box, then one would like to find it faster.Assuming there are many searchers, the authors suggest that using an algorithmthat requires no coordination between searchers can be highly beneficial.Indeed, besides saving the need for a communication and coordination mechanism,such algorithms enjoy inherent robustness. The authors proceed to solve thislinear search problem in the case of countably many boxes and an adversaryplaced treasure, and prove that the best speed-up possible by $k$non-coordinating searchers is precisely $\frac{k}{4}(1+1/k)^2$. In particular,this means that asymptotically, the speed-up is four times worse compared tothe case of full coordination.  We suggest an important variant of the problem, where the treasure is placeduniformly at random in one of a finite, large, number of boxes. We devisenon-coordinating algorithms that achieve a speed-up of $6/5$ for two searchers,a speed-up of $3/2$ for three searchers, and in general, a speed-up of$k(k+1)/(3k-1)$ for any $k \geq 1$ searchers. Thus, as $k$ grows to infinity,the speed-up approaches three times worse compared to the case of fullcoordination. Moreover, these bounds are tight in a strong sense as nonon-coordinating search algorithm for $k$ searchers can achieve betterspeed-ups. We also devise non-coordinating algorithms that use only logarithmicmemory in the size of the search domain, and yet, asymptotically, achieve theoptimal speed-up. Finally, we note that all our algorithms are extremely simpleand hence applicable.

Parallel Linear Search with no Coordination for a Randomly Placed Treasure