Optimal LP Rounding and Fast Combinatorial Algorithms for Clustering Edge-Colored Hypergraphs

Nate Veldt

Abstract

We study the approximability of an existing framework for clustering edge-colored hypergraphs, which is closely related to chromatic correlation clustering and is motivated by machine learning and data mining applications where the goal is to cluster a set of objects based on multiway interactions of different categories or types. We present improved approximation guarantees based on linear programming, and show they are tight by proving a matching integrality gap. Our results also include new approximation hardness results, a combinatorial 2-approximation whose runtime is linear in the hypergraph size, and several new connections to well-studied objectives such as vertex cover and hypergraph multiway cut.
BibTeX
@inproceedings{veldt2023optimal,
  author = {Nate Veldt},
  title = {{Optimal LP Rounding and Fast Combinatorial Algorithms for Clustering Edge-Colored Hypergraphs}},
  booktitle = {International Conference on Machine Learning},
  year = {2023},
  url = {https://openreview.net/forum?id=GsZMKt_b8jr},
}
Figure