Search papers, labs, and topics across Lattice.
This paper addresses the NP-hard preordering problem, a generalization of clustering and partial ordering relevant to bioinformatics and social network analysis. The authors introduce novel partial optimality conditions for solving the preordering problem, aiming to maximize the sum of values for ordered pairs within a preorder. Experiments on real and synthetic data demonstrate that these new conditions significantly improve the efficient identification of pairs *a, b* where *a* is not less than or equal to *b* in an optimal preorder.
Discovering non-precedence relations in preordering problems just got faster, potentially unlocking new insights in bioinformatics and social network analysis.
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.
