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

We study vertex cut and flow sparsifiers that were recently introduced byMoitra, and Leighton and Moitra. We improve and generalize their results. Wegive a new polynomial-time algorithm for constructing O(log k / log log k) cutand flow sparsifiers, matching the best existential upper bound on the qualityof a sparsifier, and improving the previous algorithmic upper bound of O(log^2k / log log k). We show that flow sparsifiers can be obtained from linearoperators approximating minimum metric extensions. We introduce the notion of(linear) metric extension operators, prove that they exist, and give an exactpolynomial-time algorithm for finding optimal operators.  We then establish a direct connection between flow and cut sparsifiers andLipschitz extendability of maps in Banach spaces, a notion studied infunctional analysis since 1930s. Using this connection, we prove a lower boundof Omega(sqrt{log k/log log k}) for flow sparsifiers and a lower bound ofOmega(sqrt{log k}/log log k) for cut sparsifiers. We show that if a certainopen question posed by Ball in 1992 has a positive answer, then there exist\tilde O(sqrt{log k}) cut sparsifiers. On the other hand, any lower bound oncut sparsifiers better than \tilde Omega(sqrt{log k}) would imply a negativeanswer to this question.

Metric Extension Operators, Vertex Sparsifiers and Lipschitz Extendability