Correlation Clustering with Constrained Cluster Sizes and Extended\n Weights Bounds

2014/11/03 by Gregory J. Puleo, Olgica Milenković, Puleo, Gregory J. +1 · 3 citations
Computer Science · Physics and Astronomy · #Advanced Clustering Algorithms Research #Advanced Graph Theory Research #Bayesian Methods and Mixture Models #Complex Network Analysis Techniques #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Machine Learning (cs.LG)

paper · pdf · doi:10.48550/arxiv.1411.0547

openalex publication_date 2014/11/03 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We consider the problem of correlation clustering on graphs with constraints\non both the cluster sizes and the positive and negative weights of edges. Our\ncontributions are twofold: First, we introduce the problem of correlation\nclustering with bounded cluster sizes. Second, we extend the regime of weight\nvalues for which the clustering may be performed with constant approximation\nguarantees in polynomial time and apply the results to the bounded cluster size\nproblem.\n

Cited by

• Algorithms and Complexity of Hedge Cluster Deletion Problems
• Online Correlation Clustering: Simultaneously Optimizing All ℓ_p-norms
• Approximate Dual Separation for the Cluster LP: a 1.387 approximation for Correlation Clustering

Related

• A Simple and Fast (3+ε)-approximation for Constrained Correlation Clustering
• A Faster Algorithm for Constrained Correlation Clustering
• Correlation Clustering for General Graphs
• Four Algorithms for Correlation Clustering: A Survey
• Fast Combinatorial Algorithms for Min Max Correlation Clustering