论文标题
在实例 - 最佳算法上，用于螺母和螺栓的概括和广义排序
On Instance-Optimal Algorithms for a Generalization of Nuts and Bolts and Generalized Sorting
论文作者
论文摘要
我们将经典的螺母和螺栓问题推广到一个设置，其中输入是$ n $螺母和$ m $螺栓的集合，并且没有任何匹配对的保证。不允许将螺母直接与螺栓直接与螺栓进行比较，而目标是进行最少的螺母螺栓比较，以发现螺母和螺栓之间的部分顺序。我们称此问题\ emph {双分排序}。 我们表明，相同尺寸的双分排序的实例表现出广泛的复杂性，并建议针对此问题进行细粒度分析。我们排除实例 - 优先性的直接概念过于严格，并采用\ emph {基于邻域}的定义。我们的定义可能具有独立的兴趣，作为对文献中存在的其他静态问题的实例 - 最佳算法的统一镜头。这包括分类（Estivill-Castro和Woods，AcmComput。1992），凸赫尔（Afshani，Barbay和Chan，JACM，2017年），自适应加入（Demaine，López-oftiz和Munro，Soda 2000）以及Graphers Gragrals and Graphers（Haleupler，Haleuplerer，ro hladek ro y haleupler，rodaine） TěTek，2023）。 作为两部分排序的主要结果，我们给出了一个随机算法，该算法在基于邻里的定义方面是实例 - 最佳W.H.P.的$ O（\ log ^3（n+m））$。 作为我们的第二个贡献，我们将二分排序概括为DAG分类，而底层DAG不一定是双方的。作为DAG排序简单算法的意外结果，我们排除了\ emph {用价格信息进行分类的潜在下限，由（Charikar，Fagin，Guruswami，Kleinberg，Kleinberg，Kleinberg，Raghavan，Raghavan和Sahai，Sahai，Stoc 2000）提出。
We generalize the classical nuts and bolts problem to a setting where the input is a collection of $n$ nuts and $m$ bolts, and there is no promise of any matching pairs. It is not allowed to compare a nut directly with a nut or a bolt directly with a bolt, and the goal is to perform the fewest nut-bolt comparisons to discover the partial order between the nuts and bolts. We term this problem \emph{bipartite sorting}. We show that instances of bipartite sorting of the same size exhibit a wide range of complexity, and propose to perform a fine-grained analysis for this problem. We rule out straightforward notions of instance-optimality as being too stringent, and adopt a \emph{neighborhood-based} definition. Our definition may be of independent interest as a unifying lens for instance-optimal algorithms for other static problems existing in literature. This includes problems like sorting (Estivill-Castro and Woods, ACM Comput. Surv. 1992), convex hull (Afshani, Barbay and Chan, JACM 2017), adaptive joins (Demaine, López-Ortiz and Munro, SODA 2000), and the recent concept of universal optimality for graphs (Haeupler, Hladík, Rozhoň, Tarjan and Tětek, 2023). As our main result on bipartite sorting, we give a randomized algorithm that is within a factor of $O(\log ^3 (n+m))$ of being instance-optimal w.h.p., with respect to the neighborhood-based definition. As our second contribution, we generalize bipartite sorting to DAG sorting, when the underlying DAG is not necessarily bipartite. As an unexpected consequence of a simple algorithm for DAG sorting, we rule out a potential lower bound on the widely-studied problem of \emph{sorting with priced information}, posed by (Charikar, Fagin, Guruswami, Kleinberg, Raghavan and Sahai, STOC 2000).
