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

Currently, the best known tradeoff between approximation ratio and complexityfor the Sparsest Cut problem is achieved by the algorithm in [Sherman, FOCS2009]: it computes $O(\sqrt{(\log n)/\varepsilon})$-approximation using$O(n^\varepsilon\log^{O(1)}n)$ maxflows for any $\varepsilon\in[\Theta(1/\logn),\Theta(1)]$. It works by solving the SDP relaxation of [Arora-Rao-Vazirani,STOC 2004] using the Multiplicative Weights Update algorithm (MW) of[Arora-Kale, JACM 2016]. To implement one MW step, Sherman approximately solvesa multicommodity flow problem using another application of MW. Nested MW stepsare solved via a certain ``chaining'' algorithm that combines results ofmultiple calls to the maxflow algorithm. We present an alternative approachthat avoids solving the multicommodity flow problem and instead computes``violating paths''. This simplifies Sherman's algorithm by removing a need fora nested application of MW, and also allows parallelization: we show how tocompute $O(\sqrt{(\log n)/\varepsilon})$-approximation via $O(\log^{O(1)}n)$maxflows using $O(n^\varepsilon)$ processors. We also revisit Sherman'schaining algorithm, and present a simpler version together with a new analysis.

A simpler and parallelizable $O(\sqrt{\log n})$-approximation algorithm for Sparsest Cut