An improved algorithm for the submodular secretary problem with a cardinality constraint

Abstract

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.

References in corpus (2)

• Constrained Submodular Maximization via a Non-symmetric Technique
• Submodular Secretary Problems: Cardinality, Matching, and Linear Constraints