Improved combinatorial approximations for weighted correlation clustering

DOI10.46298/DMTCS.12424MaRDI QIDQ6875999zbMATH OpenFDO

Authors Mojtaba Ostovari, Alireza Zarei

Publication date 13 January 2026

Published in Discrete Mathematics and Theoretical Computer Science. DMTCS (Search for Journal in Brave)

Copyright license arXiv.org Non-exclusive license to distribute

Full work available at URL https://doi.org/10.46298/DMTCS.12424

zbMATH Keywords

approximation algorithmcluster editingclustering aggregationconsensus clusteringcorrelation clustering

Mathematics Subject Classification ID

Signed and weighted graphs (05C22) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25)

Cites work

• Aggregating inconsistent information: ranking and clustering
• Cluster graph modification problems
• Clustering with qualitative information
• Correlation clustering
• Correlation clustering in general weighted graphs
• Correlation clustering with Sherali-Adams
• Handling correlated rounding error via preclustering: a 1.73-approximation for correlation clustering
• Lasserre Hierarchy, Higher Eigenvalues, and Approximation Schemes for Graph Partitioning and Quadratic Integer Programming with PSD Objectives
• Near Optimal LP Rounding Algorithm for CorrelationClustering on Complete and Complete k-partite Graphs
• Rounding Semidefinite Programming Hierarchies via Global Correlation

This page was built for publication: Improved combinatorial approximations for weighted correlation clustering

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6875999)