Correlation Clustering with Constrained Cluster Sizes and Extended Weights Bounds

DOI10.1137/140994198zbMath1337.68296arXiv1411.0547MaRDI QIDQ2947231

Olgica Milenković, Gregory J. Puleo

Publication date: 22 September 2015

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

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

zbMATH Keywords

linear programming; approximation algorithms; correlation clustering; edge weights

Mathematics Subject Classification ID

90C35: Programming involving graphs or networks

90C05: Linear programming

68W25: Approximation algorithms

Related Items

Unnamed Item, Metric-Constrained Optimization for Graph Clustering Algorithms, Approximation Algorithms for the Capacitated Min–Max Correlation Clustering Problem, A combinatorial multi-armed bandit approach to correlation clustering, Approximation algorithm for the balanced 2-correlation clustering problem on well-proportional graphs, A literature review on correlation clustering: cross-disciplinary taxonomy with bibliometric analysis, Approximation algorithms for the capacitated correlation clustering problem with penalties, An improved approximation algorithm for capacitated correlation clustering problem, Approximation algorithm for the capacitated correlation clustering problem with penalties, Approximation algorithms for two variants of correlation clustering problem, Approximation algorithms for the lower bounded correlation clustering problem

Uses Software

• AS 136
• SING

Cites Work

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