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 paper, we study parallel algorithms for the correlation clusteringproblem, where every pair of two different entities is labeled with similar ordissimilar. The goal is to partition the entities into clusters to minimize thenumber of disagreements with the labels. Currently, all efficient parallelalgorithms have an approximation ratio of at least 3. In comparison with the$1.994+\epsilon$ ratio achieved by polynomial-time sequential algorithms[CLN22], a significant gap exists.  We propose the first poly-logarithmic depth parallel algorithm that achievesa better approximation ratio than 3. Specifically, our algorithm computes a$(2.4+\epsilon)$-approximate solution and uses $\tilde{O}(m^{1.5})$ work.Additionally, it can be translated into a $\tilde{O}(m^{1.5})$-time sequentialalgorithm and a poly-logarithmic rounds sublinear-memory MPC algorithm with$\tilde{O}(m^{1.5})$ total memory.  Our approach is inspired by Awerbuch, Khandekar, and Rao's [AKR12]length-constrained multi-commodity flow algorithm, where we develop anefficient parallel algorithm to solve a truncated correlation clustering linearprogram of Charikar, Guruswami, and Wirth [CGW05]. Then we show the solution ofthe truncated linear program can be rounded with a factor of at most 2.4 lossby using the framework of [CMSY15]. Such a rounding framework can then beimplemented using parallel pivot-based approaches.

Breaking 3-Factor Approximation for Correlation Clustering in Polylogarithmic Rounds