Correlation clustering with constrained cluster sizes and extended weights bounds

DOI10.1137/140994198zbMATH Open1337.68296arXiv1411.0547OpenAlexW1958024236MaRDI QIDQ2947231FDOQ2947231

Authors: Gregory J. Puleo, Olgica Milenkovic 

Publication date: 22 September 2015

Published in: SIAM Journal on Optimization (Search for Journal in Brave)

Abstract: We consider the problem of correlation clustering on graphs with constraints on both the cluster sizes and the positive and negative weights of edges. Our contributions are twofold: First, we introduce the problem of correlation clustering with bounded cluster sizes. Second, we extend the regime of weight values for which the clustering may be performed with constant approximation guarantees in polynomial time and apply the results to the bounded cluster size problem.

Full work available at URL: https://arxiv.org/abs/1411.0547

Recommendations

• Algorithms - ESA 2003
• Correlation clustering in general weighted graphs
• Approximation algorithms for two variants of correlation clustering problem
• Correlation clustering with partial information
• A note on the inapproximability of correlation clustering

zbMATH Keywords

linear programmingapproximation algorithmscorrelation clusteringedge weights

Mathematics Subject Classification ID

Linear programming (90C05) Programming involving graphs or networks (90C35) Approximation algorithms (68W25)

Cites Work

• Algorithm AS 136: A K-Means Clustering Algorithm
• On the Implementation of a Primal-Dual Interior Point Method
• Voting schemes for which it can be difficult to tell who won the election
• Clustering with qualitative information
• Aggregating inconsistent information: ranking and clustering
• Correlation clustering
• Balanced graph partitioning
• Computational results of an interior point algorithm for large scale linear programming
• Minimal multicut and maximal integer multiflow: a survey
• On the hardness of approximating Multicut and Sparsest-Cut
• On the power of unique 2-prover 1-round games
• The Minimum Feedback Arc Set Problem is NP-Hard for Tournaments
• Aggregating inconsistent information
• Correlation clustering in general weighted graphs
• Cluster graph modification problems
• The Cluster Editing Problem: Implementations and Experiments
• Correlation clustering, maximizing agreements via semidefinite programming
• Algorithms - ESA 2003
• Correlation clustering with partial information
• Deterministic pivoting algorithms for constrained ranking and clustering problems
• Algorithms for Degree Constrained Graph Factors of Minimum Deficiency
• An Axiomatic Approach to Constructing Distances for Rank Comparison and Aggregation
• Near Optimal LP Rounding Algorithm for CorrelationClustering on Complete and Complete k-partite Graphs
• Bounded size graph clustering with applications to stream processing

Cited In (21)

• An improved approximation algorithm for capacitated correlation clustering problem
• Title not available (Why is that?)
• Correlation clustering in general weighted graphs
• Graph clustering with a constraint on cluster sizes
• Algorithms - ESA 2003
• On cluster editing problem with clusters of small sizes
• Approximation algorithm for the correlation clustering problem with non-uniform hard constrained cluster sizes
• Resource-Bounded Information Gathering for Correlation Clustering
• A combinatorial multi-armed bandit approach to correlation clustering
• An efficient local search algorithm for correlation clustering on large graphs
• An improved approximation algorithm for the capacitated correlation clustering problem
• Contraction methods for correlation clustering: the order is important
• Approximation algorithm for the balanced 2-correlation clustering problem on well-proportional graphs
• Approximation Algorithms for the Capacitated Min–Max Correlation Clustering Problem
• Approximation algorithms for the capacitated correlation clustering problem with penalties
• Approximation algorithm for the capacitated correlation clustering problem with penalties
• Approximation algorithms for two variants of correlation clustering problem
• A literature review on correlation clustering: cross-disciplinary taxonomy with bibliometric analysis
• Cost-optimal constrained correlation clustering via weighted partial maximum satisfiability
• Metric-Constrained Optimization for Graph Clustering Algorithms
• Approximation algorithms for the lower bounded correlation clustering problem

Uses Software

• AS 136
• SING

This page was built for publication: Correlation clustering with constrained cluster sizes and extended weights bounds

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2947231)