A 4-approximation algorithm for min max correlation clustering
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2023
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866917589546958848 |
|---|---|
| author | Heidrich, Holger Irmai, Jannik Andres, Bjoern |
| author_facet | Heidrich, Holger Irmai, Jannik Andres, Bjoern |
| contents | We introduce a lower bounding technique for the min max correlation clustering problem and, based on this technique, a combinatorial 4-approximation algorithm for complete graphs. This improves upon the previous best known approximation guarantees of 5, using a linear program formulation (Kalhan et al., 2019), and 40, for a combinatorial algorithm (Davies et al., 2023a). We extend this algorithm by a greedy joining heuristic and show empirically that it improves the state of the art in solution quality and runtime on several benchmark datasets. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2310_09196 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | A 4-approximation algorithm for min max correlation clustering Heidrich, Holger Irmai, Jannik Andres, Bjoern Data Structures and Algorithms Discrete Mathematics Machine Learning We introduce a lower bounding technique for the min max correlation clustering problem and, based on this technique, a combinatorial 4-approximation algorithm for complete graphs. This improves upon the previous best known approximation guarantees of 5, using a linear program formulation (Kalhan et al., 2019), and 40, for a combinatorial algorithm (Davies et al., 2023a). We extend this algorithm by a greedy joining heuristic and show empirically that it improves the state of the art in solution quality and runtime on several benchmark datasets. |
| title | A 4-approximation algorithm for min max correlation clustering |
| topic | Data Structures and Algorithms Discrete Mathematics Machine Learning |
| url | https://arxiv.org/abs/2310.09196 |