On selecting the k largest with median tests

DOI10.1007/BF01553891zbMath0664.68065OpenAlexW2059499348MaRDI QIDQ1115626

Andrew Chi-Chih Yao

Publication date: 1989

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01553891

zbMATH Keywords

selectiondecision treemedian testsminimax complexity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Searching and sorting (68P10)

Related Items (4)

Selection problems via \(m\)-ary queries ⋮ On selecting the \(k\) largest with restricted quadratic queries ⋮ Selecting the \(k\) largest elements with parity tests ⋮ Decision trees: Old and new results.

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A lower bound of \({1\over 2}n^2\) on linear search programs for the knapsack problem
• Proving simultaneous positivity of linear forms
• A Lower Bound to Finding Convex Hulls
• Lower bounds for algebraic decision trees
• Bounds for Selection
• A Counting Approach to Lower Bounds for Selection Problems

This page was built for publication: On selecting the k largest with median tests