Approximation algorithms for the capacitated correlation clustering problem with penalties

DOI10.1007/s10878-022-00930-6MaRDI QIDQ2099670

Sai Ji, Dongmei Zhang, Xianzhao Zhang, Gai-Di Li

Publication date: 24 November 2022

Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10878-022-00930-6

zbMATH Keywords

approximation algorithm; correlation clustering; LP-rounding; penalties; capacitated

Mathematics Subject Classification ID

90C59: Approximation methods and heuristics in mathematical programming

90C27: Combinatorial optimization

Cites Work

• A cutting-plane approach for large-scale capacitated multi-period facility location using a specialized interior-point method
• Correlation clustering
• Mechanism design for two-opposite-facility location games with penalties on distance
• On single-source capacitated facility location with cost and fairness objectives
• Correlation clustering in data streams
• An improved approximation algorithm for capacitated correlation clustering problem
• A constant FPT approximation algorithm for hard-capacitated \(k\)-means
• Min-max correlation clustering via multicut
• Local search approximation algorithms for the \(k\)-means problem with penalties
• Approximation algorithms for the fault-tolerant facility location problem with penalties
• Clustering with qualitative information
• Near Optimal LP Rounding Algorithm for CorrelationClustering on Complete and Complete k-partite Graphs
• Correlation Clustering with Constrained Cluster Sizes and Extended Weights Bounds
• Improved Approximation Algorithms for Bipartite Correlation Clustering
• Motif and Hypergraph Correlation Clustering
• Approximation Schemes for Capacitated Clustering in Doubling Metrics