2025/02/20 by Jannik Irmai, Irmai, Jannik, Maximilian Moeller +3 · 1 citation
Computer Science · Engineering · #Advanced Clustering Algorithms Research #Advanced Research in Systems and Signal Processing #Advanced Text Analysis Techniques #FOS: Computer and information sciences #Machine Learning (cs.LG)
paper · pdf · doi:10.48550/arxiv.2502.14536
openalex publication_date 2025/02/20 · openalex created_date 2025/02/22 · openalex updated_date 2026/07/28
The NP-hard maximum value preordering problem is both a joint relaxation and a hybrid of the clique partition problem (a clustering problem) and the partial ordering problem. Toward approximate solutions and lower bounds, we introduce a linear-time 4-approximation algorithm that constructs a maximum dicut of a subgraph and define local search heuristics. Toward upper bounds, we tighten a linear program relaxation by the class of odd closed walk inequalities that define facets, as we show, of the preorder polytope. We contribute implementations of the algorithms, apply these to the task of jointly clustering and partially ordering the accounts of published social networks, and compare the output and efficiency qualitatively and quantitatively.