An Improved Combinatorial Algorithm for Edge-Colored Clustering in Hypergraphs
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2026
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866911483117436928 |
|---|---|
| author | Han, Seongjune Veldt, Nate |
| author_facet | Han, Seongjune Veldt, Nate |
| contents | Many complex systems and datasets are characterized by multiway interactions of different categories, and can be modeled as edge-colored hypergraphs. We focus on clustering such datasets using the NP-hard edge-colored clustering problem, where the goal is to assign colors to nodes in such a way that node colors tend to match edge colors. A key focus in prior work has been to develop approximation algorithms for the problem that are combinatorial and easier to scale. In this paper, we present the first combinatorial approximation algorithm with an approximation factor better than 2. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2603_03273 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | An Improved Combinatorial Algorithm for Edge-Colored Clustering in Hypergraphs Han, Seongjune Veldt, Nate Data Structures and Algorithms Social and Information Networks Many complex systems and datasets are characterized by multiway interactions of different categories, and can be modeled as edge-colored hypergraphs. We focus on clustering such datasets using the NP-hard edge-colored clustering problem, where the goal is to assign colors to nodes in such a way that node colors tend to match edge colors. A key focus in prior work has been to develop approximation algorithms for the problem that are combinatorial and easier to scale. In this paper, we present the first combinatorial approximation algorithm with an approximation factor better than 2. |
| title | An Improved Combinatorial Algorithm for Edge-Colored Clustering in Hypergraphs |
| topic | Data Structures and Algorithms Social and Information Networks |
| url | https://arxiv.org/abs/2603.03273 |