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 Tools annual

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 Tools monthly

Global: Zendy Plus monthly

Presents the access of premium content as premium feature

Premium Content

Global: Zendy Plus annual

Global: Zendy Free Plan

We give the first quasipolynomial upper bound $\phi n^{\text{polylog}(n)}$for the smoothed complexity of the SWAP algorithm for local Graph Partitioning(also known as Bisection Width), where $n$ is the number of nodes in the graphand $\phi$ is a parameter that measures the magnitude of perturbations appliedon its edge weights. More generally, we show that the same quasipolynomialupper bound holds for the smoothed complexity of the 2-FLIP algorithm for anybinary Maximum Constraint Satisfaction Problem, including local Max-Cut, forwhich similar bounds were only known for $1$-FLIP. Our results are based on ananalysis of cycles formed in long sequences of double flips, showing that it isunlikely for every move in a long sequence to incur a positive but smallimprovement in the cut weight.

Smoothed Complexity of SWAP in Local Graph Partitioning