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 Connectivity Augmentation Problem (CAP) together with a well-knownspecial case thereof known as the Tree Augmentation Problem (TAP) are among themost basic Network Design problems. There has been a surge of interest recentlyto find approximation algorithms with guarantees below $2$ for both TAP andCAP, culminating in the currently best approximation factor for both problemsof $1.393$ through quite sophisticated techniques.  We present a new and arguably simple matching-based method for the well-knownspecial case of leaf-to-leaf instances. Combining our work with priortechniques, we readily obtain a $(\frac{4}{3}+\epsilon)$-approximation forLeaf-to-Leaf CAP by returning the better of our solution and one of an existingmethod. Prior to our work, a $\frac{4}{3}$-guarantee was only known forLeaf-to-Leaf TAP instances on trees of height $2$. Moreover, when combining ourtechnique with a recently introduced stack analysis approach, which is part ofthe above-mentioned $1.393$-approximation, we can further improve theapproximation factor to $1.29$, obtaining for the first time a factor below$\frac{4}{3}$ for a nontrivial class of TAP/CAP instances.

Better-Than-$\frac{4}{3}$-Approximations for Leaf-to-Leaf Tree and Connectivity Augmentation