On selecting the k largest with median tests
type: Item
instance of: scholarly article
title: On selecting the k largest with median tests
zbMATH Open document ID: 0664.68065
DOI: 10.1007/BF01553891
published in: Algorithmica
publication date: 1989-01-01T00:00:00Z
review text: Let \(W_ k(n)\) be the minimax complexity of selecting the k largest elements of n numbers \(x_ 1,x_ 2,...,x_ n\) by pairwise comparisons \(x_ i:x_ j\). It is well known \(W_ 2(n)=n-2+[lg n],\) and \(W_ k(n)=n+(k-1)lg n+O(1)\) for all fixed \(k\geq 3\). In this paper we study \(W_ k'(n)\), the minimax complexity of selecting the k largest, when tests of the form ``Is \(x_ i\) the median of \(\{x_ i,x_ j,x_ t\}?''\) are also allowed. It is proved that \(W_ 2'(n)=n-2+\lceil lg n\rceil,\) and \(W_ k'(n)=n+(k-1)lg_ 2 n+O(1)\) for all fixed \(k\geq 3\).
Mathematics Subject Classification ID: 68P10
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 4087038
zbMATH Keywords: median tests
zbMATH Keywords: decision tree
zbMATH Keywords: selection
zbMATH Keywords: minimax complexity
author: Andrew Chi-Chih Yao
MaRDI profile type: Publication
cites work: A lower bound of \({1\over 2}n^2\) on linear search programs for the knapsack problem
cites work: A Counting Approach to Lower Bounds for Selection Problems
cites work: Bounds for Selection
cites work: Q5601827
cites work: Q4057549
cites work: Proving simultaneous positivity of linear forms
cites work: Lower bounds for algebraic decision trees
cites work: Q5603731
cites work: A Lower Bound to Finding Convex Hulls
full work available at URL: https://doi.org/10.1007/bf01553891
OpenAlex ID: W2059499348
description: scientific article; zbMATH DE number 4087038