Tight Bounds for Sorting Under Partial Information

Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review

Abstract

Sorting is one of the fundamental algorithmic problems in theoretical computer science. It has a natural generalization, introduced by Fredman in 1976, called sorting under partial information. The input consists of: –a ground set X of size n, –a partial oracle OF (where partial oracle queries for any (xi,xj) output whether xi≺Pxj, for some partial order P), –a linear oracle OL (where linear oracle queries for any (xi,xj) output whether xi<Lxj and the order L 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: the number of linear oracle queries to OL, the number of partial oracle queries to OP, and the time spent (the number of algorithmic instructions required to identify for which pairs (xi,xj) a partial or linear oracle query is performed). Let e(P) denote the number of linear extensions of P. Any algorithm requires worst-case log2e(P) linear oracle queries to recover the linear order on X. In 1984, Kahn and Saks presented the first algorithm that uses Θ(loge(P)) linear oracle queries (using O(n2) partial oracle queries and exponential time). Since then, both the general problem and restricted variants have been consistently studied. 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 Θ(loge(P) linear oracle queries and O(n+loge(P)) time - which is worst-case optimal in the number of linear oracle queries but not in the time spent. We present the first algori...
Original languageEnglish
Title of host publicationProceedings of the 2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS)
PublisherIEEE
Publication date2024
Pages2243-2252
ISBN (Print)979-8-3315-1675-8
ISBN (Electronic)979-8-3315-1674-1
DOIs
Publication statusPublished - 2024
Event2024 IEEE 65th Annual Symposium on Foundations of Computer Science - Chicago, United States
Duration: 27 Oct 202430 Oct 2024

Conference

Conference2024 IEEE 65th Annual Symposium on Foundations of Computer Science
Country/TerritoryUnited States
CityChicago
Period27/10/202430/10/2024

Keywords

  • Sorting
  • Algorithm

Fingerprint

Dive into the research topics of 'Tight Bounds for Sorting Under Partial Information'. Together they form a unique fingerprint.

Cite this