2023/02/09 by David Stein, Stein, David, Silvia Di Gregorio +3 · 2 citations
Business, Management and Accounting · Computer Science · Physics and Astronomy · #Advanced Clustering Algorithms Research #Complex Network Analysis Techniques #Computer Vision and Pattern Recognition (cs.CV) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #Facility Location and Emergency Management #Machine Learning (cs.LG)
paper · pdf · doi:10.48550/arxiv.2302.04694
openalex publication_date 2023/02/09 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.