Correlation Clustering with Constrained Cluster Sizes and Extended Weights Bounds

DOI10.1137/140994198zbMath1337.68296arXiv1411.0547OpenAlexW1958024236MaRDI 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 programmingapproximation algorithmscorrelation clusteringedge weights

Mathematics Subject Classification ID

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

Related Items (max. 100)

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 Capacitated Min–Max Correlation Clustering Problem ⋮ Approximation algorithms for the lower bounded correlation clustering problem ⋮ A combinatorial multi-armed bandit approach to correlation clustering ⋮ Unnamed Item ⋮ 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 ⋮ Metric-Constrained Optimization for Graph Clustering Algorithms

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

This page was built for publication: Correlation Clustering with Constrained Cluster Sizes and Extended Weights Bounds