Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2310.09638 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909689501974528 |
|---|---|
| author | Ostovari, Mojtaba Zarei, Alireza |
| author_facet | Ostovari, Mojtaba Zarei, Alireza |
| contents | We present combinatorial approximation algorithms for the weighted correlation clustering problem. In this problem, we have a set of vertices and two weight values for each pair of vertices, denoting their difference and similarity. The goal is to cluster the vertices with minimum total intra-cluster difference weights plus inter-cluster similarity weights. We present two results for weighted instances with $n$ vertices:
- A randomized 3-approximation combinatorial algorithm for instances that satisfy probability constraints, running in $O(n^2)$ time. This improves the $O(n^6)$ running time of the previous best-known combinatorial approximation, a 3-approximation algorithm, introduced by Chawla et al. (2015).
- A randomized 1.6-approximation combinatorial algorithm for instances that satisfy probability and triangle inequality constraints, running in $O(n^2)$ time. This improves the longstanding combinatorial 2-approximation of Ailon et al. (2008) while matching its running time. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2310_09638 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Improved Combinatorial Approximations for Weighted Correlation Clustering Ostovari, Mojtaba Zarei, Alireza Data Structures and Algorithms We present combinatorial approximation algorithms for the weighted correlation clustering problem. In this problem, we have a set of vertices and two weight values for each pair of vertices, denoting their difference and similarity. The goal is to cluster the vertices with minimum total intra-cluster difference weights plus inter-cluster similarity weights. We present two results for weighted instances with $n$ vertices: - A randomized 3-approximation combinatorial algorithm for instances that satisfy probability constraints, running in $O(n^2)$ time. This improves the $O(n^6)$ running time of the previous best-known combinatorial approximation, a 3-approximation algorithm, introduced by Chawla et al. (2015). - A randomized 1.6-approximation combinatorial algorithm for instances that satisfy probability and triangle inequality constraints, running in $O(n^2)$ time. This improves the longstanding combinatorial 2-approximation of Ailon et al. (2008) while matching its running time. |
| title | Improved Combinatorial Approximations for Weighted Correlation Clustering |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2310.09638 |