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 study the problem of estimating the size of maximum matching and minimumvertex cover in sublinear time. Denoting the number of vertices by $n$ and theaverage degree in the graph by $\bar{d}$, we obtain the following results forboth problems:  * A multiplicative $(2+\epsilon)$-approximation that takes$\tilde{O}(n/\epsilon^2)$ time using adjacency list queries.  * A multiplicative-additive $(2, \epsilon n)$-approximation in$\tilde{O}((\bar{d} + 1)/\epsilon^2)$ time using adjacency list queries.  * A multiplicative-additive $(2, \epsilon n)$-approximation in$\tilde{O}(n/\epsilon^{3})$ time using adjacency matrix queries.  All three results are provably time-optimal up to polylogarithmic factorsculminating a long line of work on these problems.  Our main contribution and the key ingredient leading to the bounds above is anew and near-tight analysis of the average query complexity of the randomizedgreedy maximal matching algorithm which improves upon a seminal result ofYoshida, Yamamoto, and Ito [STOC'09].

Time-Optimal Sublinear Algorithms for Matching and Vertex Cover