2026-07-26T17:27:11Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:23417 2025-10-02T12:54:35Z ddc:004 open_access

Simultaneously Approximating All Norms for Massively Parallel Correlation Clustering Cao, Nairen Li, Shi Ye, Jia Correlation Clustering All-Norms Approximation Algorithm Massively Parallel Algorithm We revisit the simultaneous approximation model for the correlation clustering problem introduced by Davies, Moseley, and Newman [Davies et al., 2024]. The objective is to find a clustering that minimizes given norms of the disagreement vector over all vertices. We present an efficient algorithm that produces a clustering that is simultaneously a 63.3-approximation for all monotone symmetric norms. This significantly improves upon the previous approximation ratio of 6348 due to Davies, Moseley, and Newman [Davies et al., 2024], which works only for 𝓁_p-norms. To achieve this result, we first reduce the problem to approximating all top-k norms simultaneously, using the connection between monotone symmetric norms and top-k norms established by Chakrabarty and Swamy [Chakrabarty and Swamy, 2019]. Then we develop a novel procedure that constructs a 12.66-approximate fractional clustering for all top-k norms. Our 63.3-approximation ratio is obtained by combining this with the 5-approximate rounding algorithm by Kalhan, Makarychev, and Zhou [Kalhan et al., 2019]. We then demonstrate that with a loss of ε in the approximation ratio, the algorithm can be adapted to run in nearly linear time and in the MPC (massively parallel computation) model with poly-logarithmic number of rounds. By allowing a further trade-off in the approximation ratio to (359+ε), the number of MPC rounds can be reduced to a constant. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Nairen Cao and Shi Li and Jia Ye 2025 Is Part Of LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2025.40 urn:nbn:de:0030-drops-234171 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2025.40 eng https://creativecommons.org/licenses/by/4.0/legalcode