Approximation algorithms for two variants of correlation clustering problem
From MaRDI portal
Publication:2156281
DOI10.1007/s10878-020-00612-1zbMath1495.90155MaRDI QIDQ2156281
Yishui Wang, Sai Ji, Min Li, Da-Chuan Xu
Publication date: 18 July 2022
Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s10878-020-00612-1
approximation algorithm; correlation clustering; uncertain graphs; non-uniform hard constrained cluster sizes
90C27: Combinatorial optimization
Related Items
Approximation Algorithms for Matroid and Knapsack Means Problems, Approximation Algorithms for the Capacitated Min–Max Correlation Clustering Problem
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A 3-approximation algorithm for the facility location problem with uniform capacities
- Improved approximation algorithms for MAX \(k\)-cut and MAX BISECTION
- Correlation clustering
- Correlation clustering in data streams
- Correlation clustering in general weighted graphs
- Clustering with qualitative information
- Approximation algorithms for hard capacitated \(k\)-facility location problems
- Near Optimal LP Rounding Algorithm for CorrelationClustering on Complete and Complete k-partite Graphs
- Correlation Clustering with Constrained Cluster Sizes and Extended Weights Bounds
- Deterministic Pivoting Algorithms for Constrained Ranking and Clustering Problems
- 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
- Bi-Factor Approximation Algorithms for Hard Capacitated k-Median Problems
- Correlation Clustering and Biclustering With Locally Bounded Errors
- Aggregating inconsistent information