  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.
