Approximation algorithm for the balanced 2-correlation clustering problem on well-proportional graphs

DOI10.1007/978-3-030-57602-8_9zbMath1482.68176OpenAlexW3047638929MaRDI QIDQ2039649

Sai Ji, Ling Gai, Dong-lei Du, Da-Chuan Xu

Publication date: 5 July 2021

Full work available at URL: https://doi.org/10.1007/978-3-030-57602-8_9

zbMATH Keywords

approximation algorithmbalanced\(k\)-correlation clusteringwell-proportional graphs

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Approximation algorithms (68W25)

Related Items

A literature review on correlation clustering: cross-disciplinary taxonomy with bibliometric analysis

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Improved approximation algorithms for MAX \(k\)-cut and MAX BISECTION
• Correlation clustering
• Cluster graph modification problems
• Correlation clustering in data streams
• Correlation clustering in general weighted graphs
• 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
• Approximation Algorithms for Min-Sum k-Clustering and Balanced k-Median
• Correlation clustering with a fixed number of clusters
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• Clustering Problems on Sliding Windows
• A Streaming Algorithm for k-Means with Approximate Coreset
• Improved Approximation Algorithms for Bipartite Correlation Clustering
• On Uniform Capacitated k -Median Beyond the Natural LP Relaxation
• Better Guarantees for $k$-Means and Euclidean $k$-Median by Primal-Dual Algorithms
• Convergence of Type-Symmetric and Cut-Balanced Consensus Seeking Systems
• Bi-Factor Approximation Algorithms for Hard Capacitated k-Median Problems
• Correlation Clustering and Biclustering With Locally Bounded Errors
• Aggregating inconsistent information
• Approximation algorithm for the correlation clustering problem with non-uniform hard constrained cluster sizes