# Partial Optimality in the Preordering Problem

arXiv: https://arxiv.org/abs/2602.17346 · HTML: https://mlsanity.com/paper/2602.17346/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 3 of its 25 references that are in the map.
- First posted on arXiv 19 Feb 2026.

## Builds on (most cited first, 3 of 3)

- [Combinatorial persistency criteria for multicut and max-cut](https://mlsanity.com/paper/1812.01426/) (2018)
- [Partial Optimality in Cubic Correlation Clustering](https://mlsanity.com/paper/2302.04694/) (2023)
- [Algorithms for the preordering problem and their application to the task of jointly clustering and ordering the accounts of a social network](https://mlsanity.com/paper/2502.14536/) (2025)

## Abstract (arXiv)

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 cab ∈ ℝ 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 notlesssim b in an optimal preorder.