TY - JOUR

T1 - New results for the k-secretary problem

AU - Albers, Susanne

AU - Ladewig, Leon

N1 - Publisher Copyright:
© 2021 The Authors

PY - 2021/4/8

Y1 - 2021/4/8

N2 - 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→∞. 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≥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 derive its competitive ratios for k≤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.

AB - 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→∞. 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≥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 derive its competitive ratios for k≤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.

KW - Online algorithms

KW - Random order model

KW - Secretary problem

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

U2 - 10.1016/j.tcs.2021.02.022

DO - 10.1016/j.tcs.2021.02.022

M3 - Article

AN - SCOPUS:85101624080

SN - 0304-3975

VL - 863

SP - 102

EP - 119

JO - Theoretical Computer Science

JF - Theoretical Computer Science

ER -