An improved approximation algorithm for capacitated correlation clustering problem

DOI10.1007/978-3-030-92681-6_4OpenAlexW4206818585MaRDI QIDQ2149853

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

Publication date: 29 June 2022

Full work available at URL: https://doi.org/10.1007/978-3-030-92681-6_4

zbMATH Keywords

approximation algorithmcorrelation clusteringLP-roundingcapacitated correlation clustering

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Related Items (1)

Approximation algorithms for the capacitated correlation clustering problem with penalties

Cites Work

• Unnamed Item
• A cutting-plane approach for large-scale capacitated multi-period facility location using a specialized interior-point method
• Correlation clustering
• On single-source capacitated facility location with cost and fairness objectives
• 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
• Approximation Schemes for Capacitated Clustering in Doubling Metrics
• Aggregating inconsistent information

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