1
$\begingroup$

$S$ is a set of $n$ elements with some unknown strict total order. The goal is to discover the greatest $k$ elements, where each step consists of comparing $m\ge 2$ elements at once (so if we compare $a, b,$ and $c$, we might get $b > c > a$). Any strategy for achieving this will have some worst-case number of steps $t$, and our strategy needs to minimize $t$ for the given $n, m,$ and $k$.

This is a generalization of the fastest horses problem, the solution of which can be partially extended to any case with $n=m^2$, and we are left with finding the top $k-1$ elements of $k^2-1$ elements, with the same value for $m$, but we also already know how some of the elements compare, ending up with a structure like:

*>*>*>*

*>*>*>*
V
*>*>*
V
*>*
V
*

The problem is proving that a given solution is optimal without an exponential-time brute force search of strategies. Even just proving that starting with the initial strategy I described is always optimal would be very helpful.

$\endgroup$
  • 1
    $\begingroup$ Is this simply the generalized $k$ fastest horses problem? $\endgroup$ – ryan Nov 12 '17 at 1:04
  • 1
    $\begingroup$ Also, to clarify, you're not looking for minimum number of comparisons, you're looking for minimum number of calls to this $m$-ary function that return a total order on the $m$ elements, correct? You may want to rephrase your title. $\endgroup$ – ryan Nov 12 '17 at 1:53
  • $\begingroup$ @ryan Yep, that was the inspiration for my exploration of the generalization. And it is the number of calls to the $m$-ary function that counts. $\endgroup$ – Fricative Melon Nov 12 '17 at 1:56
  • $\begingroup$ The exact optimum probably isn't known in general, though there are some conjectures stating that the optimum isn't far away from the trivial lower bound. See for example en.wikipedia.org/wiki/1/3%E2%80%932/3_conjecture. $\endgroup$ – Yuval Filmus Nov 12 '17 at 11:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.