Approximation algorithms for two variants of correlation clustering problem
Authors: 
Sai Ji, Dachuan Xu, Min Li, Yishui WangAuthors Info & Claims
Pages 933 - 952
Abstract
Correlation 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 correlation clustering problem: correlation clustering problem on uncertain graphs and correlation clustering problem with non-uniform hard constrained cluster sizes. Both problems overcome part of the limitations of the existing variants of correlation clustering problem and have practical applications in the real world. We provide a constant approximation algorithm and two approximation algorithms for the former and the latter problem, respectively.
References
[1]
Amit N (2004) The bicluster graph editing problem. Diss, Tel Aviv University
[2]
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
[3]
Achtert E, Böhm C, David J, Kröger P, and Zimek A Global correlation clustering based on the hough transform Stat Anal Data Min 2010 1 3 111-127
[4]
Ahn K J, Cormode G, Guha S, Mcgregor A, Wirth A (2015) Correlation clustering in data streams. In: Proceedings of the 32th International Conference on International Conference on Machine Learning (ICML), pp 2237-2246
[5]
Ailon N, Charikar M, and Newman A Aggregating inconsistent information: ranking and clustering J ACM 2008 55 5 1-27 Article No. 23
[6]
Arthur D, Vassilvitskii S (2007) k-Means++: the advantages of careful seeding. In: Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp 1027-1035
[7]
Aggarwal A, Louis A, Bansal M, Garg N, Gupta N, Gupta S, and Jain S A 3-approximation algorithm for the facility location problem with uniform capacities Math Program 2013 141 1–2 527-547
[8]
Ahmadian S, Norouzi-Fard A, Svensson O, Ward J (2017) Better guarantees for -means and euclidean -median by primal-dual algorithms. In: Proceedings of the 58th Annual Symposium on Foundations of Computer Science (FOCS), pp 61-72
[9]
Aardal K, van den Berg PL, Gijswijt D, and Li S Approximation algorithms for hard capacitated k-facility location problems Eur J Oper Res 2015 242 2 358-368
[10]
Bonchi F Overlapping correlation clustering Knowl Inf Syst 2013 35 1 1-32
[11]
Bansal N, Blum A, and Chawla S Correlation clustering Mach learn 2004 56 1–3 89-113
[12]
Byrka J, Fleszar K, Rybicki B, Spoerhase J (2015) Bi-factor approximation algorithms for hard capacitated -median problems. In: Proceedings of the 26th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp 722-736
[13]
Braverman V, Lang H, Levin K, Monemizadeh M (2016) Clustering problems on sliding windows. In: Proceedings of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp 1374-1390
[14]
Ceccarello M, Fantozzi C, Pietracaprina A, Pucci G, and Vandin F Clustering uncertain graphs Proc VLDB Endow 2017 11 4 472-484
[15]
Charikar M, Guruswami V, and Wirth A Clustering with qualitative information J Comp Syst Sci 2005 71 3 360-383
[16]
Chawla S, Makarychev K, Schramm T, Yaroslavtsev G (2015) Near optimal LP rounding algorithm for correlationclustering on complete and complete k-partite graphs. In: Proceedings of the 47th annual ACM symposium on Theory of computing (STOC), pp 219-228
[17]
Demaine E, Emanuel D, Fiat A, and Immorlica N Correlation clustering in general weighted graphs Theor Comp Sci 2006 361 2 172-187
[18]
Frieze A and Jerrum M Improved approximation algorithms for maxk-cut and max bisection Algorithmica 1997 18 1 67-81
[19]
Giotis I, Guruswami V (2006) Correlation clustering with a fixed number of clusters. In: Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp 1167-1176
[20]
Goemans MX and Williamson DP Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming J ACM 1995 42 6 1115-1145
[21]
Gu Y, Gao C, Cong G, and Yu G Effective and efficient clustering methods for correlated probabilistic graphs IEEE Trans Knowl Data Eng 2013 26 5 1117-1130
[22]
Kollios G, Potamias M, and Terzi E Clustering large probabilistic graphs IEEE Trans Knowl Data Eng 2011 25 2 325-336
[23]
Li S On uniform capacitated -median beyond the natural LP relaxation ACM Trans Algorithms 2017 13 2 1-18 Article No. 22
[24]
Li M, Xu D, Zhang D, Zhang T (2019) A streaming algorithm for -Means with approximate coreset. Asia Pac J Oper Res 36:1950006:1–1950006:18
[25]
Mathieu C, Schudy W (2010) Correlation clustering with noisy input. In: Proceedings of the 21th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp 712-728
[26]
Mathieu C, Sankur O, and Schudy W Online correlation clustering Comput Stat 2010 21 2 211-229
[27]
Newman MEJ Finding community structure in networks using the eigenvectors of matrices Phys Rev E 2006 74 3 036104
[28]
Puleo GJ and Milenkovic O Correlation clustering with constrained cluster sizes and extended weights bounds SIAM J Optim 2015 25 3 1857-1872
[29]
Puleo GJ and Milenkovic O Correlation clustering and biclustering with locally bounded errors IEEE Trans Inf Theory 2018 64 6 4105-4119
[30]
Pal M, Tardos T, Wexler T (2001) Facility location with nonuniform hard capacities. In: Proceedings of the 42nd Annual Symposium on Foundations of Computer Science (FOCS), pp 329-338
[31]
Swamy C (2004) Correlation clustering: Maximizing agreements via semidefinite programming. In: Proceedings of the 15th Annual ACM-SIAM symposium on Discrete Algorithms (SODA), pp 526-527
[32]
Williamson ZDP Deterministic pivoting algorithms for constrained ranking and clustering problems Math Oper Res 2009 34 3 594-620
[33]
Zhang C, Yarkony J, Hamprecht F A (2014) Cell detection and segmentation using correlation clustering. In: Proceedings of the 17th International Conference on Medical Image Computing and Computer-Assisted Intervention (MICCAI), pp 9-16
Index Terms
- Approximation algorithms for two variants of correlation clustering problem
Index terms have been assigned to the content through auto-classification.
Recommendations
Approximation Algorithm for the Correlation Clustering Problem with Non-uniform Hard Constrained Cluster Sizes
Algorithmic Aspects in Information and ManagementAbstractThis paper considers the correlation clustering problem with non-uniform hard constrained cluster sizes, which is a generalization of correlation clustering problem. In this problem, we are given a positive integer for each vertex v, and ...
Approximation Algorithms for the Lower Bounded Correlation Clustering Problem
Computational Data and Social NetworksAbstractLower 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 ...
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
© Springer Science+Business Media, LLC, part of Springer Nature 2020.
Publisher
Springer-Verlag
Berlin, Heidelberg
Publication History
Published: 01 July 2022
Author Tags
Qualifiers
- Research-article
Funding Sources
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