DROPS

Artifact

Software

JGDoerrer/selection_generator

Authors: Josua Dörrer, Konrad Gendle, Johanna Betz, Julius von Smercek, Andreas Steding, and Florian Stober

Abstract

Cite as

Josua Dörrer, Konrad Gendle, Johanna Betz, Julius von Smercek, Andreas Steding, Florian Stober. JGDoerrer/selection_generator (Software, Source Code). Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@misc{dagstuhl-artifact-23788,
   title = {{JGDoerrer/selection\underlinegenerator}}, 
   author = {D\"{o}rrer, Josua and Gendle, Konrad and Betz, Johanna and von Smercek, Julius and Steding, Andreas and Stober, Florian},
   note = {Software, swhId: \href{https://archive.softwareheritage.org/swh:1:dir:abb8051290f859ac8ff2ff5b01f18f4cef1d05ae;origin=https://github.com/JGDoerrer/selection_generator;visit=swh:1:snp:748620e215c47e1e425f3d4c244336c97afc8341;anchor=swh:1:rev:ca3b75668047a916a9801d12ac4f8d77b5feda3c}{\texttt{swh:1:dir:abb8051290f859ac8ff2ff5b01f18f4cef1d05ae}} (visited on 2025-07-15)},
   url = {https://github.com/JGDoerrer/selection_generator},
   doi = {10.4230/artifacts.23788},
}

Document

DOI: 10.4230/LIPIcs.SEA.2025.16

Exact Lower Bounds for the Number of Comparisons in Selection

Authors: Josua Dörrer, Konrad Gendle, Johanna Betz, Julius von Smercek, Andreas Steding, and Florian Stober

Published in: LIPIcs, Volume 338, 23rd International Symposium on Experimental Algorithms (SEA 2025)

Abstract

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.

Cite as

Josua Dörrer, Konrad Gendle, Johanna Betz, Julius von Smercek, Andreas Steding, and Florian Stober. Exact Lower Bounds for the Number of Comparisons in Selection. In 23rd International Symposium on Experimental Algorithms (SEA 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 338, pp. 16:1-16:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{dorrer_et_al:LIPIcs.SEA.2025.16,
  author =	{D\"{o}rrer, Josua and Gendle, Konrad and Betz, Johanna and von Smercek, Julius and Steding, Andreas and Stober, Florian},
  title =	{{Exact Lower Bounds for the Number of Comparisons in Selection}},
  booktitle =	{23rd International Symposium on Experimental Algorithms (SEA 2025)},
  pages =	{16:1--16:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-375-1},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{338},
  editor =	{Mutzel, Petra and Prezza, Nicola},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2025.16},
  URN =		{urn:nbn:de:0030-drops-232547},
  doi =		{10.4230/LIPIcs.SEA.2025.16},
  annote =	{Keywords: selection, lower bounds, exhaustive computer search}
}

Search Results

Documents authored by Betz, Johanna

JGDoerrer/selection_generator

Abstract

Cite as

Exact Lower Bounds for the Number of Comparisons in Selection

Abstract

Cite as

Thanks for your feedback!

Could not send message