License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ISAAC.2019.18
URN: urn:nbn:de:0030-drops-115142
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2019/11514/
Albers, Susanne ;
Ladewig, Leon
New Results for the k-Secretary 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 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.
BibTeX - Entry
@InProceedings{albers_et_al:LIPIcs:2019:11514,
author = {Susanne Albers and Leon Ladewig},
title = {{New Results for the k-Secretary Problem}},
booktitle = {30th International Symposium on Algorithms and Computation (ISAAC 2019)},
pages = {18:1--18:19},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-130-6},
ISSN = {1868-8969},
year = {2019},
volume = {149},
editor = {Pinyan Lu and Guochuan Zhang},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2019/11514},
URN = {urn:nbn:de:0030-drops-115142},
doi = {10.4230/LIPIcs.ISAAC.2019.18},
annote = {Keywords: Online algorithms, secretary problem, random order model}
}
|
Keywords: |
|
Online algorithms, secretary problem, random order model |
|
Collection: |
|
30th International Symposium on Algorithms and Computation (ISAAC 2019) |
|
Issue Date: |
|
2019 |
|
Date of publication: |
|
28.11.2019 |
