Partial Optimality in the Preordering Problem

2026/02/19 by David Stein, Jannik Irmai, Bjoern Andres · 1 voice
Computer Science · #cs.DM #cs.DS #cs.LG

paper · pdf · doi:10.48550/arxiv.2602.17346

arxiv published 2026/02/19 · arxiv updated 2026/05/13

Abstract

Preordering is a generalization of clustering and partial ordering with applications in bioinformatics and social network analysis. Given a finite set V and a value c_ab ∈ ℝ for every ordered pair ab of elements of V, the preordering problem asks for a preorder \lesssim on V that maximizes the sum of the values of those pairs ab for which a \lesssim b. Building on the state of the art in solving this NP-hard problem partially, we contribute new partial optimality conditions and efficient algorithms for deciding these conditions. In experiments with real and synthetic data, these new conditions increase, in particular, the fraction of pairs ab for which it is decided efficiently that a \not\lesssim b in an optimal preorder.

Citations

• Algorithms for the preordering problem and their application to the task of jointly clustering and ordering the accounts of a social network
• Partial Optimality in Cubic Correlation Clustering
• Combinatorial persistency criteria for multicut and max-cut
• Maximum Persistency in Energy Minimization

Discussions

• David Stein, Jannik Irmai, Bjoern Andres: Partial Optimality in the Preordering Problem https://arxiv.org/abs/2602.17346 https://arxiv.org/pdf/2602.17346 https://arxiv.org/html/2602.17346 [bsky, 0 points, 0 comments]

Related

• Algorithms for the preordering problem and their application to the task of jointly clustering and ordering the accounts of a social network
• Sorting under partial (interval order) information
• Distances Between Partial Preference Orderings
• Derivations of large classes of facet-defining inequalities of the weak order polytope using ranking structures
• Tight Universal Bounds for Partially Presorted Pareto Front and Convex Hull