论文标题
最佳的LP圆形和线性时间近似算法，用于聚类边缘色超图
Optimal LP Rounding and Linear-Time Approximation Algorithms for Clustering Edge-Colored Hypergraphs
论文作者
论文摘要
我们研究了聚类边缘色超图的现有框架的近似性，该框架与色度相关聚类密切相关，并由机器学习和数据挖掘应用程序激励，该应用程序是基于不同类别或类型的多路相互作用的一组对象。我们提出了基于线性编程的改进的近似保证，并通过证明匹配的完整性差距来表明它们很紧张。我们的结果还包括新的近似硬度结果，一个组合2-示例，其运行时在超图尺寸中是线性的，以及与良好的目标（例如顶点盖和HyperGraph Multiway Cut）的几个新连接。
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.
