论文标题
局部相关聚类和异构层次群集的不适当性
Inapproximability for Local Correlation Clustering and Dissimilarity Hierarchical Clustering
论文作者
论文摘要
我们提出了与局部目标相关性聚类以及与差异信息的分层聚类相关性群集的近似结果的硬度。对于前者，我们研究了Puleo和Milenkovic（ICML '16）的本地目标，该目标优先考虑减少最坏的数据点的分歧，而对于后者，我们研究了Dasgupta成本函数的最大化版本（STOC '16）。我们的APX硬度结果表明，这两个问题很难在4/3〜1.33（假设p vs np）和9159/9189〜0.9967（假设唯一的游戏猜想）之内。
We present hardness of approximation results for Correlation Clustering with local objectives and for Hierarchical Clustering with dissimilarity information. For the former, we study the local objective of Puleo and Milenkovic (ICML '16) that prioritizes reducing the disagreements at data points that are worst off and for the latter we study the maximization version of Dasgupta's cost function (STOC '16). Our APX hardness results imply that the two problems are hard to approximate within a constant of 4/3 ~ 1.33 (assuming P vs NP) and 9159/9189 ~ 0.9967 (assuming the Unique Games Conjecture) respectively.
