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

We consider the classic Correlation Clustering problem: Given a completegraph where edges are labelled either $+$ or $-$, the goal is to find apartition of the vertices that minimizes the number of the \pedges across partsplus the number of the \medges within parts. Recently, Cohen-Addad, Lee andNewman [CLN22] presented a 1.994-approximation algorithm for the problem usingthe Sherali-Adams hierarchy, hence breaking through the integrality gap of 2for the classic linear program and improving upon the 2.06-approximation ofChawla, Makarychev, Schramm and Yaroslavtsev [CMSY15].  We significantly improve the state-of-the-art by providing a1.73-approximation for the problem. Our approach introduces a preclustering ofCorrelation Clustering instances that allows us to essentially ignore the errorarising from the {\em correlated rounding} used by [CLN22]. This additionalpower simplifies the previous algorithm and analysis. More importantly, itenables a new {\em set-based rounding} that complements the previous roundings.A combination of these two rounding algorithms yields the improved bound.

Handling Correlated Rounding Error via Preclustering: A 1.73-approximation for Correlation Clustering