Approximation Algorithms for the Lower Bounded Correlation Clustering Problem
Authors: 
Sai Ji, Yinhong Dong, Donglei Du, Dachuan XuAuthors Info & Claims
Pages 39 - 49
Abstract
Lower bounded correlation clustering problem is a generalization of the classical correlation clustering problem, which has many applications in protein interaction networks, cross-lingual link detection, and communication networks, etc. In the lower bounded correlation clustering problem, we are given a complete graph and an integer L. Each edge is labelled either by a positive sign or a negative sign − whenever the two endpoints of the edge are similar or dissimilar respectively. The goal of this problem is to partition the vertex set into several clusters, subject to an lower bound L on the sizes of clusters so as to minimize the number of disagreements, which is the total number of the edges with positive labels between clusters and the edges with negative labels within clusters. In this paper, we propose the lower bounded correlation clustering problem and formulate the problem as an integer program. Furthermore, we provide two polynomial time algorithms with constant approximate ratios for the lower bounded correlation clustering problem on some special graphs.
References
[1]
Ailon N, Avigdor-Elgrabli N, Liberty E, and Zuylen AV Improved approximation algorithms for bipartite correlation clustering SIAM J. Comput. 2012 41 5 1110-1121
[2]
Ahmadi S, Khuller S, and Saha B Lodi A and Nagarajan V Min-max correlation clustering via MultiCut Integer Programming and Combinatorial Optimization 2019 Cham Springer 13-26
[3]
Ahmadian S and Swamy C Erlebach T and Persiano G Improved approximation guarantees for lower-bounded facility location Approximation and Online Algorithms 2013 Heidelberg Springer 257-271
[4]
Bansal N, Blum A, and Chawla S Correlation clustering Mach. Learn. 2004 56 1–3 89-113
[5]
Bonchi F, Gionis A, Gullo F, Tsourakakis CE, and Ukkonen A Chromatic correlation clustering ACM Trans. Knowl. Discov. Data 2015 9 4 1-24
[6]
Bonchi F, Gionis A, and Ukkonen A Overlapping correlation clustering Knowl. Inf. Syst. 2013 35 1 1-32
[7]
Charikar M, Guruswami V, and Wirth A Clustering with qualitative information J. Comput. Syst. Sci. 2005 71 3 360-383
[8]
Chawla, S., Makarychev, K., Schramm, T., Yaroslavtsev, G.: Near optimal LP rounding algorithm for correlation clustering on complete and complete -partite graphs. In: Proceedings of the 47th ACM Symposium on Theory of Computing, pp. 219–228 (2015)
[9]
Fukunaga T LP-based pivoting algorithm for higher-order correlation clustering J. Comb. Optim. 2018 37 4 1312-1326
[10]
Han L, Hao C, Wu C, and Zhang Z Kim D, Uma RN, Cai Z, and Lee DH Approximation algorithms for the lower-bounded k-median and its generalizations Computing and Combinatorics 2020 Cham Springer 627-639
[11]
Jafarov, J., Kalhan, S., Makarychev, K., Makarychev, Y.: Correlation clustering with asymmetric classification errors. In: Proceedings of the 37th International Conference on Machine Learning, pp. 4641–4650 (2020)
[12]
Li, S.: On facility location with general lower bounds. In: Proceedings of the 30th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 2279–2290 (2019)
[13]
Li P, Puleo GJ, and Milenkovic O Motif and hypergraph correlation clustering IEEE Trans. Inf. Theory 2019 66 5 3065-3078
[14]
Makarychev, K., Makarychev, Y., Vijayaraghavan, A.: Correlation clustering with noisy partial information. In: Proceedings of the 28th Annual Conference Computational Learning Theory, pp. 1321–1342 (2015)
[15]
Mathieu, C., Schudy, W.: Correlation clustering with noisy input. In: Proceedings of the 21th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 712–728 (2010)
[16]
Puleo GJ and Milenkovic O Correlation clustering with constrained cluster sizes and extended weights bounds SIAM J. Optim. 2015 25 3 1857-1872
[17]
Svitkina Z Lower-bounded facility location ACM Trans. Algorithms 2010 6 4 1-16
[18]
Swamy, C.: Correlation clustering: maximizing agreements via semidefinite programming. In: Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 526–527 (2004)
[19]
Saha, B., Subramanian, S.: Correlation clustering with same-cluster queries bounded by optimal cost. In: Proceedings of the 27th Annual European Symposium on Algorithms, pp. 81:1–81:17 (2019)
[20]
Veldt, N., Gleich, D.F., Wirth, A.: A correlation clustering framework for community detection. In: Proceedings of the 27th World Wide Web Conference, pp. 439–448 (2018)
Recommendations
Approximation algorithms for the lower bounded correlation clustering problem
AbstractLower bounded correlation clustering problem (LBCorCP) is a new generalization of the correlation clustering problem (CorCP). In the LBCorCP, we are given an integer L and a complete labelled graph. Each edge in the graph is either positive or ...
Approximation algorithms for two variants of correlation clustering problem
AbstractCorrelation clustering problem is a clustering problem which has many applications such as protein interaction networks, cross-lingual link detection, communication networks, and social computing. In this paper, we introduce two variants of ...
An Improved Approximation Algorithm for Capacitated Correlation Clustering Problem
Combinatorial Optimization and Applications
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Nov 2021
391 pages
© Springer Nature Switzerland AG 2021.
Publisher
Springer-Verlag
Berlin, Heidelberg
Publication History
Published: 15 November 2021
Author Tags
Qualifiers
- Article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 14 Nov 2024
Other Metrics
Citations
View Options
View options
Get Access
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in