Albers, Susanne ;
Ladewig, Leon
New Results for the kSecretary Problem
Abstract
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 ksecretary problem, which includes the classical secretary problem with the special case k=1. It is wellknown 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 ksecretary 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.
BibTeX  Entry
@InProceedings{albers_et_al:LIPIcs:2019:11514,
author = {Susanne Albers and Leon Ladewig},
title = {{New Results for the kSecretary Problem}},
booktitle = {30th International Symposium on Algorithms and Computation (ISAAC 2019)},
pages = {18:118:19},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771306},
ISSN = {18688969},
year = {2019},
volume = {149},
editor = {Pinyan Lu and Guochuan Zhang},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2019/11514},
URN = {urn:nbn:de:0030drops115142},
doi = {10.4230/LIPIcs.ISAAC.2019.18},
annote = {Keywords: Online algorithms, secretary problem, random order model}
}
2019
Keywords: 

Online algorithms, secretary problem, random order model 
Seminar: 

30th International Symposium on Algorithms and Computation (ISAAC 2019)

Issue date: 

2019 
Date of publication: 

2019 