We study the submodular secretary problem with a cardinality constraint. In this problem, $n$ candidates for secretaries appear sequentially in random order. At the arrival of each candidate, a decision maker must irrevocably decide whether to hire him. The decision maker aims to hire at most $k$ candidates that maximize a non-negative submodular set function. We propose an $(\mathrm{ e} - 1)^2 / (\mathrm{ e}^2 (1 + \mathrm{ e}))$-competitive algorithm for this problem, which improves the best one known so far.
Categories: cs.DS