Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2023
|
| Soggetti: | |
| Accesso online: | https://arxiv.org/abs/2310.09638 |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
Sommario:
- 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.