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 this paper, we present a low-diameter decomposition algorithm in the LOCALmodel of distributed computing that succeeds with probability $1 - 1/poly(n)$.Specifically, we show how to compute an $\left(\epsilon, O\left(\frac{\logn}{\epsilon}\right)\right)$ low-diameter decomposition in$O\left(\frac{\log^3(1/\epsilon)\log n}{\epsilon}\right)$ round  Further developing our techniques, we show new distributed algorithms forapproximating general packing and covering integer linear programs in the LOCALmodel. For packing problems, our algorithm finds an $(1-\epsilon)$-approximatesolution in $O\left(\frac{\log^3 (1/\epsilon) \log n}{\epsilon}\right)$ roundswith probability $1 - 1/poly(n)$. For covering problems, our algorithm finds an$(1+\epsilon)$-approximate solution in $O\left(\frac{\left(\log \log n + \log(1/\epsilon)\right)^3 \log n}{\epsilon}\right)$ rounds with probability $1 -1/poly(n)$. These results improve upon the previous $O\left(\frac{\log^3n}{\epsilon}\right)$-round algorithm by Ghaffari, Kuhn, and Maus [STOC 2017]which is based on network decompositions.  Our algorithms are near-optimal for many fundamental combinatorial graphoptimization problems in the LOCAL model, such as minimum vertex cover andminimum dominating set, as their $(1\pm \epsilon)$-approximate solutionsrequire $\Omega\left(\frac{\log n}{\epsilon}\right)$ rounds to compute.

The Complexity of Distributed Approximation of Packing and Covering Integer Linear Programs