Suppose that $n$ items arrive online in random order and the goal is to
select $k$ of them such that the expected sum of the selected items is
maximized. The decision for any item is irrevocable and must be made on arrival
without knowing future items. This problem is known as the $k$-secretary
problem, which includes the classical secretary problem with the special case
$k=1$. It is well-known that the latter problem can be solved by a simple
algorithm of competitive ratio $1/e$ which is optimal for $n \to \infty$.
Existing algorithms beating the threshold of $1/e$ either rely on involved
selection policies already for $k=2$, or assume that $k$ is large.
In this paper we present results for the $k$-secretary problem, considering
the interesting and relevant case that $k$ is small. We focus on simple
selection algorithms, accompanied by combinatorial analyses. As a main
contribution we propose a natural deterministic algorithm designed to have
competitive ratios strictly greater than $1/e$ for small $k \geq 2$. This
algorithm is hardly more complex than the elegant strategy for the classical
secretary problem, optimal for $k=1$, and works for all $k \geq 1$. We derive
its competitive ratios for $k \leq 100$, ranging from $0.41$ for $k=2$ to
$0.75$ for $k=100$.
Moreover, we consider an algorithm proposed earlier in the literature, for
which no rigorous analysis is known. We show that its competitive ratio is
$0.4168$ for $k=2$, implying that the previous analysis was not tight. Our
analysis reveals a surprising combinatorial property of this algorithm, which
might be helpful to find a tight analysis for all $k$.

该论文研究了 $k$- 秘书问题，提出了一种自然的确定性算法，其竞争比率均高于 $1 /e$，并针对 $ k $ 较小的情况进行了分析。