Correlation clustering with constrained cluster sizes and extended weights bounds
From MaRDI portal
Publication:2947231
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.
Recommendations
Cites work
- Aggregating inconsistent information
- Aggregating inconsistent information: ranking and clustering
- Algorithm AS 136: A K-Means Clustering Algorithm
- Algorithms - ESA 2003
- Algorithms for Degree Constrained Graph Factors of Minimum Deficiency
- An Axiomatic Approach to Constructing Distances for Rank Comparison and Aggregation
- Balanced graph partitioning
- Bounded size graph clustering with applications to stream processing
- Cluster graph modification problems
- Clustering with qualitative information
- Computational results of an interior point algorithm for large scale linear programming
- Correlation clustering
- Correlation clustering in general weighted graphs
- Correlation clustering with partial information
- Correlation clustering, maximizing agreements via semidefinite programming
- Deterministic pivoting algorithms for constrained ranking and clustering problems
- Minimal multicut and maximal integer multiflow: a survey
- Near Optimal LP Rounding Algorithm for CorrelationClustering on Complete and Complete k-partite Graphs
- On the Implementation of a Primal-Dual Interior Point Method
- On the hardness of approximating Multicut and Sparsest-Cut
- On the power of unique 2-prover 1-round games
- The Cluster Editing Problem: Implementations and Experiments
- The Minimum Feedback Arc Set Problem is NP-Hard for Tournaments
- Voting schemes for which it can be difficult to tell who won the election
Cited in
(21)- An improved approximation algorithm for capacitated correlation clustering problem
- Correlation clustering in general weighted graphs
- scientific article; zbMATH DE number 7561398 (Why is no real title available?)
- 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
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)
