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

We give a poly-time algorithm for the $k$-edge-connected spanning subgraph($k$-ECSS) problem that returns a solution of cost no greater than the cheapest$(k+10)$-ECSS on the same graph. Our approach enhances the iterative relaxationframework with a new ingredient, which we call ghost values, that allows forhigh sparsity in intermediate problems.  Our guarantees improve upon the best-known approximation factor of $2$ for$k$-ECSS whenever the optimal value of $(k+10)$-ECSS is close to that of$k$-ECSS. This is a property that holds for the closely related problem$k$-edge-connected spanning multi-subgraph ($k$-ECSM), which is identical to$k$-ECSS except edges can be selected multiple times at the same cost. As aconsequence, we obtain a$\left(1+O\left(\frac{1}{k}\right)\right)$-approximation algorithm for$k$-ECSM, which resolves a conjecture of Pritchard and improves upon a recent$\left(1+O\left(\frac{1}{\sqrt{k}}\right)\right)$-approximation algorithm ofKarlin, Klein, Oveis Gharan, and Zhang. Moreover, we present a matching lowerbound for $k$-ECSM, showing that our approximation ratio is tight up to theconstant factor in $O\left(\frac{1}{k}\right)$, unless $P=NP$.

Ghost Value Augmentation for $k$-ECSS and $k$-ECSM