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

In this note, we describe a $\alpha_{GW} + \tilde{\Omega}(1/d^2)$-factorapproximation algorithm for Max-Cut on weighted graphs of degree $\leq d$.Here, $\alpha_{GW}\approx 0.878$ is the worst-case approximation ratio of theGoemans-Williamson rounding for Max-Cut. This improves on previous results forunweighted graphs by Feige, Karpinski, and Langberg and Flor\'en. Our guaranteeis obtained by a tighter analysis of the solution obtained by applying anatural local improvement procedure to the Goemans-Williamson rounding of thebasic SDP strengthened with triangle inequalities.

Approximating Max-Cut on Bounded Degree Graphs: Tighter Analysis of the FKL Algorithm