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

Connectivity augmentation problems are among the most elementary questions inNetwork Design. Many of these problems admit natural $2$-approximationalgorithms, often through various classic techniques, whereas it remains openwhether approximation factors below $2$ can be achieved. One of the most basicexamples thereof is the Weighted Connectivity Augmentation Problem (WCAP). InWCAP, one is given an undirected graph together with a set of additionalweighted candidate edges, and the task is to find a cheapest set of candidateedges whose addition to the graph increases its edge-connectivity. We present a$(1.5+\varepsilon)$-approximation algorithm for WCAP, showing for the firsttime that factors below $2$ are achievable.  On a high level, we design a well-chosen local search algorithm, inspired byrecent advances for Weighted Tree Augmentation. To measure progress, weconsider a directed weakening of WCAP and show that it has highly structuredplanar solutions. Interpreting a solution of the original problem as one ofthis directed weakening allows us to describe local exchange steps in a cleanand algorithmically amenable way. Leveraging these insights, we show that wecan efficiently search for good exchange steps within a component class forlink sets that is closely related to bounded treewidth subgraphs of circlegraphs. Moreover, we prove that an optimum solution can be decomposed intosmaller components, at least one of which leads to a good local search step aslong as we did not yet achieve the claimed approximation guarantee.

A $(1.5+\epsilon)$-Approximation Algorithm for Weighted Connectivity Augmentation