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

Given a graph $G$ of degree $k$ over $n$ vertices, we consider the problem ofcomputing a near maximum cut or a near minimum bisection in polynomial time.For graphs of girth $2L$, we develop a local message passing algorithm whosecomplexity is $O(nkL)$, and that achieves near optimal cut values among all$L$-local algorithms. Focusing on max-cut, the algorithm constructs a cut ofvalue $nk/4+ n\mathsf{P}_\star\sqrt{k/4}+\mathsf{err}(n,k,L)$, where$\mathsf{P}_\star\approx 0.763166$ is the value of the Parisi formula from spinglass theory, and $\mathsf{err}(n,k,L)=o_n(n)+no_k(\sqrt{k})+n \sqrt{k} o_L(1)$(subscripts indicate the asymptotic variables). Our result generalizes tolocally treelike graphs, i.e., graphs whose girth becomes $2L$ after removing asmall fraction of vertices.  Earlier work established that, for random $k$-regular graphs, the typicalmax-cut value is $nk/4+ n\mathsf{P}_\star\sqrt{k/4}+o_n(n)+no_k(\sqrt{k})$.Therefore our algorithm is nearly optimal on such graphs. An immediatecorollary of this result is that random regular graphs have nearly minimummax-cut, and nearly maximum min-bisection among all regular locally treelikegraphs. This can be viewed as a combinatorial version of the near-Ramanujanproperty of random regular graphs.

Local algorithms for Maximum Cut and Minimum Bisection on locally treelike regular graphs of large degree