Approximation algorithm for the capacitated correlation clustering problem with penalties

DOI10.1007/978-3-030-93176-6_2zbMath1503.90111MaRDI QIDQ2151358

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

Publication date: 1 July 2022

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

zbMATH Keywords

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

Mathematics Subject Classification ID

90C35: Programming involving graphs or networks

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
• 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