An improved approximation algorithm for the capacitated correlation clustering problem

DOI10.1142/s0129054123410010MaRDI QIDQ6610093

Sai Ji, Yu-kun Cheng, Zhongrui Zhao, Jingjing Tan

Publication date: 24 September 2024

Published in: International Journal of Foundations of Computer Science (Search for Journal in Brave)

zbMATH Keywords

clustering problemapproximation algorithmsLP-roundingcapacitated correlation clustering

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27)

Cites Work

• Unnamed Item
• Correlation clustering
• Correlation clustering in data streams
• Min-max correlation clustering via multicut
• Clustering with qualitative information
• Approximating $k$-Median via Pseudo-Approximation
• Near Optimal LP Rounding Algorithm for CorrelationClustering on Complete and Complete k-partite Graphs
• Correlation Clustering with Constrained Cluster Sizes and Extended Weights Bounds
• Local Search Yields Approximation Schemes for $k$-Means and $k$-Median in Euclidean and Minor-Free Metrics
• Improved Approximation Algorithms for Bipartite Correlation Clustering
• Better Guarantees for $k$-Means and Euclidean $k$-Median by Primal-Dual Algorithms
• Aggregating inconsistent information

This page was built for publication: An improved approximation algorithm for the capacitated correlation clustering problem