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

In this paper, we consider the following graph partitioning problem: Theinput is an undirected graph $G=(V,E),$ a balance parameter $b \in (0,1/2]$ anda target conductance value $\gamma \in (0,1).$ The output is a cut which, ifnon-empty, is of conductance at most $O(f),$ for some function $f(G, \gamma),$and which is either balanced or well correlated with all cuts of conductance atmost $\gamma.$ Spielman and Teng gave an $\tilde{O}(|E|/\gamma^{2})$-timealgorithm for $f= \sqrt{\gamma \log^{3}|V|}$ and used it to decompose graphsinto a collection of near-expanders. We present a new spectral algorithm forthis problem which runs in time $\tilde{O}(|E|/\gamma)$ for $f=\sqrt{\gamma}.$Our result yields the first nearly-linear time algorithm for the classicBalanced Separator problem that achieves the asymptotically optimalapproximation guarantee for spectral methods. Our method has the advantage ofbeing conceptually simple and relies on a primal-dual semidefinite-programmingSDP approach. We first consider a natural SDP relaxation for the BalancedSeparator problem. While it is easy to obtain from this SDP a certificate ofthe fact that the graph has no balanced cut of conductance less than $\gamma,$somewhat surprisingly, we can obtain a certificate for the stronger correlationcondition. This is achieved via a novel separation oracle for our SDP and byappealing to Arora and Kale's framework to bound the running time. Our resultcontains technical ingredients that may be of independent interest.

Towards an SDP-based Approach to Spectral Methods: A Nearly-Linear-Time Algorithm for Graph Partitioning and Decomposition