Optimal LP Rounding and Linear-Time Approximation Algorithms for Clustering Edge-Colored Hypergraphs
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.
Cite
Text
Veldt. "Optimal LP Rounding and Linear-Time Approximation Algorithms for Clustering Edge-Colored Hypergraphs." International Conference on Machine Learning, 2023.Markdown
[Veldt. "Optimal LP Rounding and Linear-Time Approximation Algorithms for Clustering Edge-Colored Hypergraphs." International Conference on Machine Learning, 2023.](https://mlanthology.org/icml/2023/veldt2023icml-optimal/)BibTeX
@inproceedings{veldt2023icml-optimal,
title = {{Optimal LP Rounding and Linear-Time Approximation Algorithms for Clustering Edge-Colored Hypergraphs}},
author = {Veldt, Nate},
booktitle = {International Conference on Machine Learning},
year = {2023},
pages = {34924-34951},
volume = {202},
url = {https://mlanthology.org/icml/2023/veldt2023icml-optimal/}
}