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.
%0 Journal Article
%1 Stein2023-vx
%A Stein, David
%A Di Gregorio, Silvia
%A Andres, Bjoern
%D 2023
%I arXiv
%J Proceedings of the 40th International Conference on Machine Learning, PMLR
%K topic_visualcomputing
%P 32598-32617
%T Partial optimality in cubic correlation clustering
%U https://proceedings.mlr.press/v202/stein23a.html
%V 202
%X 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.
@article{Stein2023-vx,
abstract = {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.},
added-at = {2024-09-10T10:41:24.000+0200},
author = {Stein, David and Di Gregorio, Silvia and Andres, Bjoern},
biburl = {https://puma.scadsai.uni-leipzig.de/bibtex/26f23823cb0c85368a3ab0fa4e5ae49be/scadsfct},
interhash = {f155df97610db3cf11c1b97814f6ef5b},
intrahash = {6f23823cb0c85368a3ab0fa4e5ae49be},
journal = {Proceedings of the 40th International Conference on Machine Learning, PMLR },
keywords = {topic_visualcomputing},
pages = {32598-32617},
publisher = {arXiv},
timestamp = {2024-11-29T12:15:58.000+0100},
title = {Partial optimality in cubic correlation clustering},
url = {https://proceedings.mlr.press/v202/stein23a.html },
volume = 202,
year = 2023
}
