提出新判据，更快判断预序关系中哪些元素不可能有先后顺序。
Partial Optimality in the Preordering Problem
- 基于新部分最优性条件，设计高效判定算法
- 实测数据中可识别更多确定不满足顺序关系的元素对
- 适合处理生物信息与社交网络中的排序问题
预序问题是聚类与部分排序的推广，广泛应用于生物信息学和社交网络分析。给定有限集合 $V$ 及每对有序元素 $ab$ 的实数值 $c_{ab}$，目标是寻找一个预序 $ hesim$ 以最大化满足 $a hesim b$ 的配对 $ab$ 的总值。针对此 NP-hard 问题的局部求解现状，本文提出新的部分最优性条件，并设计高效算法来判断这些条件。在真实与合成数据上的实验表明，新条件显著提升了可高效判定为 $a ot hesim b$ 的元素对比例。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。