**Originators: ** Immanuel McLaughlin
(presented by Immanuel McLaughlin - REGS 2010)

**Definitions:**
Given an unknown linear ordering *T*, a *k-ary comparison* returns
the linear ordering among *k* specified elements from *T*. Let
*S(n,k,t)* be the minimum number of *k*-ary comparisons needed to
guarantee determining the top *t* elements of *T* in order.

**Background: **
The case *k=2* reduces to traditional binary comparison sorting, about
which much is known (see [K], for example). Optimal algorithms are known for
*S(n,2,t)* when *t≤3*, and asymptotically optimal algorithms are
known for larger values of *t*.

**Problem 1:** Compute *S(n,k,t)*, at least asymptotically.

**Comments:**
A straightforward generalization of the optimal algorithm for finding the top
two elements when *k=2* yields *S(n,k,2) ≤
*⌈*(n-1)/(k-1)*⌉ + ⌈log* _{k}n*⌉-1.
For

**Problem 2:**
How many *k*-ary comparisons are needed to guarantee finding the
*s*-th largest element of *T*?

**Comments:** This problem also is much studied for *k=2*,
Again, generalizing known results for *k=2* should offer a good starting
point.

**References:**

[A1] M. Aigner, Producing posets, Discrete Math. 35 (1981) 1-15.

[A2] M. Aigner, Selecting the top three elements, Discrete Appl. Math. 4
(1982) 247-267.

[K] D.E. Knuth, The Art of Computer Programming, Vol. 3, Sorting and
Searching (Addison-Wesley, Reading, MA 1973).

L. Hyafil, Bounds for selection, SIAM J. Comput. 5 (1976) 109-l 14.