The higher-order correlation clustering problem is an expressive model, and recently, local search heuristics have been proposed for several applications. Certifying optimality, however, is NP-hard and practically hampered already by the complexity of the problem statement. Here, we focus on establishing partial optimality conditions for the special case of complete graphs and cubic objective functions. In addition, we define and implement algorithms for testing these conditions and examine their effect numerically, on two datasets.
翻译:高阶相关聚类问题是一个具有表现力的模型,最近已经提出了局部搜索启发式算法来解决几种应用。然而,证明最优性是NP难问题,实际上这已经受到问题陈述复杂性的限制。在这里,我们专注于建立完全图和立方目标函数的特殊情况下的局部最优性条件。此外,我们定义和实现了用于测试这些条件的算法,并在两个数据集上进行了数值分析。