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 the $k$-edge-connected spanning subgraph ($k$ECSS) problem, our goal is tocompute a minimum-cost sub-network that is resilient against up to $k$ linkfailures: Given an $n$-node $m$-edge graph with a cost function on the edges,our goal is to compute a minimum-cost $k$-edge-connected spanning subgraph.This NP-hard problem generalizes the minimum spanning tree problem and is the"uniform case" of a much broader class of survival network design problems(SNDP). A factor of two has remained the best approximation ratio forpolynomial-time algorithms for the whole class of SNDP, even for a special caseof $2$ECSS. The fastest $2$-approximation algorithm is however rather slow,taking $O(mn k)$ time [Khuller, Vishkin, STOC'92]. A faster time complexity of$O(n^2)$ can be obtained, but with a higher approximation guarantee of $(2k-1)$[Gabow, Goemans, Williamson, IPCO'93].  Our main contribution is an algorithm that $(1+\epsilon)$-approximates theoptimal fractional solution in $\tilde O(m/\epsilon^2)$ time (independent of$k$), which can be turned into a $(2+\epsilon)$ approximation algorithm thatruns in time $\tilde O\left(\frac{m}{\epsilon^2} +\frac{k^2n^{1.5}}{\epsilon^2}\right)$ for (integral) $k$ECSS; this improves therunning time of the aforementioned results while keeping the approximationratio arbitrarily close to a factor of two.

Approximating k-Edge-Connected Spanning Subgraphs via a Near-Linear Time LP Solver