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

This paper makes two main contributions: The first is the construction of anear-minimum spanning tree with constant average distortion. The second is ageneral equivalence theorem relating two refined notions of distortion: scalingdistortion and prioritized distortion.  Minimum Spanning Trees of weighted graphs are fundamental objects in numerousapplications. In particular in distributed networks, the minimum spanning treeof the network is often used to route messages between network nodes.Unfortunately, while being most efficient in the total cost of connecting allnodes, minimum spanning trees fail miserably in the desired property ofapproximately preserving distances between pairs. While known lower boundsexclude the possibility of the worst case distortion of a tree being small, itwas shown in [ABN15] that there exists a spanning tree with constant averagedistortion. Yet, the weight of such a tree may be significantly larger thanthat of the MST. In this paper, we show that any weighted undirected graphadmits a {\em spanning tree} whose weight is at most $(1+\rho)$ times that ofthe MST, providing {\em constant average distortion} $O(1/\rho)$. Our resultexhibits the best possible tradeoff of this type.  This result makes use of a general equivalence theorem relating two recentlydeveloped notions of distortion for metric embedding. The first is the notionof scaling distortion, which provides improved distortion for $1-\epsilon$fractions of the pairs, for all $\epsilon$ simultaneously. A stronger versioncalled coarse scaling distortion, has improved distortion guarantees for thefurthest pairs. The second notion is that of prioritized distortion, a propertyallowing to prioritize the nodes whose associated distortions will be improved.We show that prioritized distortion is essentially equivalent to coarse scalingdistortion via a general transformation.

On Notions of Distortion and an Almost Minimum Spanning Tree with Constant Average Distortion