A Unified Lower Bound for Selection and Set Partitioning Problems

DOI10.1145/322234.322245zbMath0454.68076OpenAlexW1967794701MaRDI QIDQ3902518

David G. Kirkpatrick

Publication date: 1981

Published in: Journal of the ACM (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/322234.322245

zbMATH Keywords

analysis of algorithmsHasse diagramcomparison treeadversary strategy

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Searching and sorting (68P10) Graph theory (including graph drawing) in computer science (68R10) Discrete mathematics in relation to computer science (68R99)

Related Items (16)

Select with Groups of 3 or 4 ⋮ Progress in selection ⋮ Optimal Parallel Algorithms For Multiselection On Mesh-Connected Computers ⋮ On computing an optimal permutation of ranks for multiselection ⋮ Architecture independent parallel selection with applications to parallel priority queues ⋮ Unnamed Item ⋮ A note on upper bounds for the selection problem ⋮ Selecting the \(k\) largest elements with parity tests ⋮ Optimal parallel selection in sorted matrices ⋮ Errata to ``Selecting the top three elements by M. Aigner: A result of a computer-assisted proof search ⋮ On partial sorting in restricted rounds ⋮ Finding a mediocre player ⋮ A selectable sloppy heap ⋮ Randomized selection in \(n+C+o(n)\) comparisons ⋮ Selection Algorithms with Small Groups ⋮ Closing a Long-Standing Complexity Gap for Selection: V 3(42) = 50

This page was built for publication: A Unified Lower Bound for Selection and Set Partitioning Problems