2024/04/12 by Ivor van der Hoog, van der Hoog, Ivor, Daniel Rutschmann +1 · 2 citations
Computer Science · #Algorithms and Data Compression #Machine Learning and Algorithms #Complexity and Algorithms in Graphs
paper · pdf · doi:10.48550/arxiv.2404.08468
Sorting has a natural generalization where the input consists of: (1) a ground set X of size n, (2) a partial oracle OP specifying some fixed partial order P on X and (3) a linear oracle OL specifying a linear order L that extends P. The goal is to recover the linear order L on X using the fewest number of linear oracle queries. In this problem, we measure algorithmic complexity through three metrics: oracle queries to OL, oracle queries to OP, and the time spent. Any algorithm requires worst-case log2 e(P) linear oracle queries to recover the linear order on X. Kahn and Saks presented the first algorithm that uses Θ(log e(P)) linear oracle queries (using O(n2) partial oracle queries and exponential time). The state-of-the-art for the general problem is by Cardinal, Fiorini, Joret, Jungers and Munro who at STOC'10 manage to separate the linear and partial oracle queries into a preprocessing and query phase. They can preprocess P using O(n2) partial oracle queries and O(n2.5) time. Then, given OL, they uncover the linear order on X in Θ(log e(P)) linear oracle queries and O(n + log e(P)) time -- which is worst-case optimal in the number of linear oracle queries but not in the time spent. For c ≥ 1, our algorithm can preprocess OP using O(n1 + (1)/(c)) queries and time. Given OL, we uncover L using Θ(c log e(P)) queries and time. We show a matching lower bound, as there exist positive constants (α, β) where for any constant c ≥ 1, any algorithm that uses at most α⋅ n1 + (1)/(c) preprocessing must use worst-case at least β⋅ c log e(P) linear oracle queries. Thus, we solve the problem of sorting under partial information through an algorithm that is asymptotically tight across all three metrics.