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 to 1 r+1 , present another novel dependentrounding algorithm with an approximation ratio of 1/⌈ k 2 ⌉, 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.

Recall the definition of a hypergraph H: it contains a set V of vertices and a collection E of "hyperedges", where