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

This paper ties the line of work on algorithms that find anO(sqrt(log(n)))-approximation to the sparsest cut together with the line ofwork on algorithms that run in sub-quadratic time by using onlysingle-commodity flows. We present an algorithm that simultaneously achievesboth goals, finding an O(sqrt(log(n)/eps))-approximation using O(n^eps log^O(1)n) max-flows. The core of the algorithm is a stronger, algorithmic version ofArora et al.'s structure theorem, where we show that matching-chaining argumentat the heart of their proof can be viewed as an algorithm that finds goodaugmenting paths in certain geometric multicommodity flow networks. By usingthat specialized algorithm in place of a black-box solver, we are able to solvethose instances much more efficiently. We also show the cut-matching gameframework can not achieve an approximation any better than Omega(log(n)/loglog(n)) without re-routing flow.

Breaking the Multicommodity Flow Barrier for sqrt(log(n))-Approximations to Sparsest Cut