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/

Zendy Plus

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

Zendy Tools

Zendy Open

The basic goal of survivable network design is to build cheap networks thatguarantee the connectivity of certain pairs of nodes despite the failure of afew edges or nodes. A celebrated result by Jain [Combinatorica'01] provides a2-approximation for a wide class of these problems. However nothing better isknown even for very basic special cases, raising the natural question whetherany improved approximation factor is possible at all.  In this paper we address one of the most basic problems in this family forwhich 2 is still the best-known approximation factor, the Forest AugmentationProblem (FAP): given an undirected unweighted graph (that w.l.o.g. is a forest)and a collection of extra edges (links), compute a minimum cardinality subsetof links whose addition to the graph makes it 2-edge-connected. Severalbetter-than-2 approximation algorithms are known for the special case where theinput graph is a tree, a.k.a. the Tree Augmentation Problem (TAP). Recentlythis was achieved also for the weighted version of TAP, and for thek-edge-connectivity generalization of TAP. These results heavily exploit thefact that the input graph is connected, a condition that does not hold in FAP.  In this paper we breach the 2-approximation barrier for FAP. Our result isbased on two main ingredients. First, we describe a reduction to the PathAugmentation Problem (PAP), the special case of FAP where the input graph is acollection of disjoint paths. Our reduction is not approximation preserving,however it is sufficiently accurate to improve on a factor 2 approximation.Second, we present a better-than-2 approximation algorithm for PAP, an openproblem on its own. Here we exploit a novel notion of implicit credits whichmight turn out to be helpful in future related work.

Breaching the 2-Approximation Barrier for the Forest Augmentation Problem