TY - GEN

T1 - New results for the k-secretary problem

AU - Albers, Susanne

AU - Ladewig, Leon

N1 - Publisher Copyright:
© Susanne Albers and Leon Ladewig; licensed under Creative Commons License CC-BY

PY - 2019/12

Y1 - 2019/12

N2 - Suppose that n numbers 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 asymptotically optimal. When k is small, only for k = 2 does there exist an algorithm beating the threshold of 1/e [Chan et al. SODA 2015]. The algorithm relies on an involved selection policy. Moreover, there exist results when k is large [Kleinberg SODA 2005]. 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 ≥ 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 ≥ 1. We explicitly compute its competitive ratios for 2 ≤ k ≤ 100, ranging from 0.41 for k = 2 to 0.75 for k = 100. Moreover, we show that an algorithm proposed by Babaioff et al. [APPROX 2007] has a competitive ratio of 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 for a tight analysis of this algorithm for general k.

AB - Suppose that n numbers 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 asymptotically optimal. When k is small, only for k = 2 does there exist an algorithm beating the threshold of 1/e [Chan et al. SODA 2015]. The algorithm relies on an involved selection policy. Moreover, there exist results when k is large [Kleinberg SODA 2005]. 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 ≥ 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 ≥ 1. We explicitly compute its competitive ratios for 2 ≤ k ≤ 100, ranging from 0.41 for k = 2 to 0.75 for k = 100. Moreover, we show that an algorithm proposed by Babaioff et al. [APPROX 2007] has a competitive ratio of 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 for a tight analysis of this algorithm for general k.

KW - Online algorithms

KW - Random order model

KW - Secretary problem

UR - http://www.scopus.com/inward/record.url?scp=85076360106&partnerID=8YFLogxK

U2 - 10.4230/LIPIcs.ISAAC.2019.18

DO - 10.4230/LIPIcs.ISAAC.2019.18

M3 - Conference contribution

AN - SCOPUS:85076360106

T3 - Leibniz International Proceedings in Informatics, LIPIcs

BT - 30th International Symposium on Algorithms and Computation, ISAAC 2019

A2 - Lu, Pinyan

A2 - Zhang, Guochuan

PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing

T2 - 30th International Symposium on Algorithms and Computation, ISAAC 2019

Y2 - 8 December 2019 through 11 December 2019

ER -