ICALP 2024 | 广义偏序集排序

广义排序是一个排序问题的变种，与排序问题相同，算法接受待排序的元素作为输入，需要对给定的元素进行次数尽可能少的比较，来揭示这些元素之间所有的大小关系，即给出它们按照大小关系的排序。与最基本的排序问题不同的是，排序算法只能从输入中给定的元素对中选择需要进行比较的对象，没有在输入中给出的元素对都无法直接进行比较。

本文将广义排序问题拓展到偏序集上，待排序的元素不再拥有一个全序，排序算法接受可以进行直接比较的元素对作为输入，通过尽可能少的比较来推断出所有输入元素对之间的大小关系。

作为广义排序问题的推广，广义偏序集问题显著地难于原问题。在广义排序问题中，由于待排序的元素之间的大小关系是全序，尽管排序算法只能选择给定的元素对进行比较，但每次都会得到形如  或  的确定回答。而在广义偏序集排序问题中，排序算法可能会得到“  不可比”的回答，而一对不可比的元素为排序提供的信息量非常小，大大提高了排序的难度。我们也可以对输入进行限制，保证每一对可以直接比较的元素在偏序集中都是可比的，我们将这种仅有可比边的广义偏序集排序问题简记为 GPSC 问题。

带比较代价的排序问题是广义排序问题在另一个方向上的推广。在带比较代价的排序问题中，比较任意两个元素  都需要付出  的代价，其中代价函数  在输入中给定。广义排序问题就是所有比较代价都是1或正无穷的特殊情况。该问题曾被认为不存在亚线性近似比的算法，但 [Goswami, Jacob, 2022] 的研究表明这种说法并不准确。在排序算法里，一般认为最优解必须要比较每一对相邻的元素对来确认这个全序的正确性，在这种最优解的定义下之前的反例并不成立。

在广义偏序集排序问题中，排序算法接受一个  个点  条边的无向图作为输入，无向图的点集表示待排序的元素集，而无向图的边集表示排序算法可以比较的元素对。排序算法的目标是使用最少的比较次数推断出每条边的两个端点之间的大小关系，并以一张有向图的形式输出。由于广义偏序集排序是偏序集排序问题的推广，因此任何排序算法都至少需要  次询问才能完成排序，其中  是排序算法输出的有向图的最长反链长度（即最大的任意两点间都不存在路径的点集）。

由于一般图上的广义偏序集排序问题难以解决，本文主要研究了随机图和完全二分图上的广义偏序集问题：

随机图：当输入无向图是某个极小有向无环图与随机图  的并时，本文提出了一种可以在  次比较内完成排序的算法。（极小即  这三条有向边不会同时都存在）当该算法被用于解决随机图上的广义排序问题时（即  的特例），该算法的比较次数为  ，接近于最优算法的比较次数  。

完全二分图：由于一般二分图上的广义偏序集排序问题与原问题同等困难，本文主要考虑输入无向图是完全二分图的情况，并提出了一种可以在  次询问内完成排序的算法。

在 GPSC 问题中，由于每个可以直接比较的元素对在偏序集中都是可比的，我们可以对广义排序算法的一些思路进行推广来解决 GPSC 问题。本文提出了一种可以在  次比较内完成排序的算法，接近于目前广义排序问题的最优结果  次比较。

在带比较代价的排序问题中，我们可以将无向图中的边按照某个阈值划分为较便宜的边和较贵的边，所有便宜的边共同构成了一个偏序集，对这个偏序集排序就是一个 GPSC 子问题。通过猜测合适的阈值，我们可以将带比较代价的排序问题转化为若干个 GPSC 子问题来求解。最终的近似比为  ，其中  为比较代价的取值种类数。该算法是第一个在比较代价有常数种取值时能实现亚线性近似比的算法。

图文 | 张宇博

北京大学姜少峰课题组