Journal
JOURNAL OF COMBINATORIAL OPTIMIZATION
Volume 43, Issue 5, Pages 933-952Publisher
SPRINGER
DOI: 10.1007/s10878-020-00612-1
Keywords
Correlation clustering; Uncertain graphs; Non-uniform hard constrained cluster sizes; Approximation algorithm
Funding
- National Natural Science Foundation of China [61433012]
- Higher Educational Science and Technology Program of Shandong Province [J17KA171]
- Natural Science Foundation of Shandong Province [ZR2019MA032]
Ask authors/readers for more resources
This paper introduces two variants of the correlation clustering problem and provides corresponding approximation algorithms. These problems have significant practical implications.
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.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available