Edge-colored Clustering in Hypergraphs: A MaxECC Approximation

摘要

We study the \maxecc\ problem, where given an edge-colored hypergraph with $k$ colors and edge size $r$, we seek to color the vertices of the graph in order to maximize the number of satisfied edges (edges having the same color as their extremities): this is an effective mechanism for clustering (coloring) objects based on their multi-way interactions with one another in a system, providing significant applications in machine learning, clustering, and data mining. We exponentially improve upon the approximation ratio of an existing algorithm, by Crane et al. present in ICML 2025, to $\frac{1}{r+1}$, present another novel dependent-rounding algorithm with an approximation ratio of $1/ \lceil \frac{k}{2}\rceil$, and modify the initial algorithm via analytical scaling techniques in order to achieve an approximation factor of $(1-e^{-r})/r$. We then apply our scaling algorithm to graph \maxecc\ and improve the best-known approximation factor for all hypergraphs: in particular, our algorithm provides an approximation factor of $0.43$ as opposed to the previously-known $0.38$ factor for graphs.