2026-07-25T12:38:53Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:23254 2025-10-27T10:36:18Z ddc:004 open_access

Exact Lower Bounds for the Number of Comparisons in Selection Dörrer, Josua Gendle, Konrad Betz, Johanna von Smercek, Julius Steding, Andreas Stober, Florian selection lower bounds exhaustive computer search Selection is the problem of finding the i-th smallest element among n elements. We apply computer search to find optimal algorithms for small instances of the selection problem. Using new algorithmic ideas, we establish tighter lower bounds for the number of comparisons required, denoted as V_i(n). Our results include optimal algorithms for n up to 15 and arbitrary i, and for n = 16 when i ≤ 6. We determine the precise values V₇(14) = 25, V₆(15) = V₇(15) = 26, and V₈(15) = 27, where previously, only a range was known. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Josua Dörrer and Konrad Gendle and Johanna Betz and Julius von Smercek and Andreas Steding and Florian Stober 2025 Is Part Of LIPIcs, Volume 338, 23rd International Symposium on Experimental Algorithms (SEA 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SEA.2025.16 urn:nbn:de:0030-drops-232547 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2025.16 eng https://creativecommons.org/licenses/by/4.0/legalcode