Selection under partial information

Abstract

The selection problem asks to find the $k$-th smallest element in a given set $X$. Its complexity is well-known to be $Θ(|X|)$ for every fixed $k$. We consider the poset selection problem where a partial order $P$ on $X$ is given, and the underlying order of $X$ is guaranteed to be a linear extension of $P$. This generalizes several variants of the selection problem studied before. Our main result is an algorithm that performs $O( k + \operatorname{OPT}(P,k) )$ comparisons, where $\operatorname{OPT}(P,k)$ is the minimum number of comparisons required for the input $(P,k)$. If $P$ is a rooted tree, we obtain an $O( \operatorname{OPT} \log (k / \operatorname{OPT}) )$ algorithm, which can be further improved to $O( \operatorname{OPT} \log \log (k/\operatorname{OPT}) )$ or $O( \operatorname{OPT} \log \operatorname{OPT})$ under mild assumptions about $P$. Our algorithms are based on the work of Kaplan, Kozma, Zamir, and Zwick [SOSA 2019], who used Chazelle's soft heaps [J. ACM 2000] to simplify several older results. We introduce a new soft heap variant, the weighted soft heap, which allows greater control over which elements get corrupted.

The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.

More in Data Structures & Algorithms

• arXiv preprint · 23 October 2026

  Beyond 3SUM-Hardness for Geometric Problems

  Nick Fischer
• arXiv preprint · 24 October 2026

  Approximation algorithms for identical parallel machine scheduling with assignment costs

  Wei Li
• arXiv preprint · 23 October 2026

  The Exact Robustness of Smith's Rule with Predicted Processing Times

  Ohad Ayalon and Ilan Reuven Cohen
• arXiv preprint · 24 October 2026

  A Factor-6 Truthful-in-Expectation Mechanism for Cascade Position Auctions

  Qiuyu Chen and Baao Xie
• arXiv preprint · 23 October 2026

  Exact Algorithms and Complexity of the Smallest Grammar Problem

  Xiangle Chen

All new papers in Data Structures & Algorithms