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 area of computing with uncertainty considers problems where someinformation about the input elements is uncertain, but can be obtained usingqueries. For example, instead of the weight of an element, we may be given aninterval that is guaranteed to contain the weight, and a query can be performedto reveal the weight. While previous work has considered models where queriesare asked either sequentially (adaptive model) or all at once (non-adaptivemodel), and the goal is to minimize the number of queries that are needed tosolve the given problem, we propose and study a new model where $k$ queries canbe made in parallel in each round, and the goal is to minimize the number ofquery rounds. We use competitive analysis and present upper and lower bounds onthe number of query rounds required by any algorithm in comparison with theoptimal number of query rounds. Given a set of uncertain elements and a familyof $m$ subsets of that set, we present an algorithm for determining the valueof the minimum of each of the subsets that requires at most $(2+\varepsilon)\cdot \mathrm{opt}_k+\mathrm{O}\left(\frac{1}{\varepsilon} \cdot \lg m\right)$rounds for every $0<\varepsilon<1$, where $\mathrm{opt}_k$ is the optimalnumber of rounds, as well as nearly matching lower bounds. For the problem ofdetermining the $i$-th smallest value and identifying all elements with thatvalue in a set of uncertain elements, we give a $2$-round-competitivealgorithm. We also show that the problem of sorting a family of sets ofuncertain elements admits a $2$-round-competitive algorithm and this is thebest possible.

Round-Competitive Algorithms for Uncertainty Problems with Parallel Queries