Abstract:
Maximum selection under probabilistic queries
\emph{(probabilistic maximization)} is a fundamental algorithmic problem
arising in numerous theoretical and practical contexts.
We derive the first query-optimal sequential algorithm for
probabilistic-maximization.
Departing from previous assumptions,
the algorithm and performance guarantees
apply even for infinitely many items, hence in particular do
not require a-priori knowledge of the number of items.
The algorithm has linear query complexity,
and is optimal also in the streaming setting.
To derive these results we consider a probabilistic setting where several candidates
for a position are asked multiple questions with the goal of
finding who has the highest probability of answering interview
questions correctly. Previous work minimized the total number
of questions asked by alternating back and forth between the
best performing candidates,
in a sense, inviting them to multiple interviews. We
show that the same order-wise selection accuracy can be achieved by
querying the candidates sequentially, never returning to a previously
queried candidate. Hence one interview is enough!