![[2602.17346] Partial Optimality in the Preordering Problem](https://arxiv.org/static/browse/0.3.4/images/arxiv-logo-fb.png){kind=logo}
[2602.17346] Partial Optimality in the Preordering Problem
Summary
This paper explores the preordering problem, a complex issue in discrete mathematics, presenting new conditions and algorithms to enhance partial optimality in clustering applications.
Why It Matters
Understanding the preordering problem is crucial for advancements in fields like bioinformatics and social network analysis, where efficient data organization can lead to better insights. The proposed algorithms could significantly improve decision-making processes in these areas.
Key Takeaways
- Introduces new partial optimality conditions for the preordering problem.
- Presents efficient algorithms that enhance decision-making in clustering.
- Demonstrates improved performance in experiments with real and synthetic data.
Computer Science > Discrete Mathematics arXiv:2602.17346 (cs) [Submitted on 19 Feb 2026] Title:Partial Optimality in the Preordering Problem Authors:David Stein, Jannik Irmai, Bjoern Andres View a PDF of the paper titled Partial Optimality in the Preordering Problem, by David Stein and 2 other authors View PDF HTML (experimental) 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} \in \mathbb{R}$ 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. Subjects: Discrete Mathematics (cs.DM); Data Structures and Algorithms (cs.DS); Machine Learning (cs.LG) Cite as: arXiv:2602.17346 [cs.DM] (or arXiv:2602.17346v1 [cs.DM] for this version) https://doi.org/10.48550/arXiv.2602.17346 Focus to learn more arXiv-issued DOI via DataCite (pending registration) Submission history From: David Stein [view email] [v1] Thu, 19 Feb 2026 13:29:09 UT...
