New results for the k-secretary problem

DOI10.1016/J.TCS.2021.02.022MaRDI QIDQ2658048zbMATH OpenOpenAlexFDO

Authors Susanne Albers, Leon Ladewig

Publication date 18 March 2021

Published in Theoretical Computer Science (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/2012.00488

zbMATH Keywords

online algorithmsrandom order modelsecretary problem

Mathematics Subject Classification ID

Stopping times; optimal stopping problems; gambling theory (60G40) Online algorithms; streaming algorithms (68W27)

Abstract: 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 $noinfty$. 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 $kgeq2$. This algorithm is hardly more complex than the elegant strategy for the classical secretary problem, optimal for $k=1$, and works for all $kgeq1$. We derive its competitive ratios for $kleq100$, 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$.

Recommendations

• A multiple-choice secretary algorithm with applications to online auctions
• Revealing Optimal Thresholds for Generalized Secretary Problem via Continuous LP: Impacts on Online K-Item Auction and Bipartite K-Matching with Random Arrival Order
• Improved algorithms and analysis for secretary problems and generalizations
• Secretary Problems via Linear Programming
• Online k-max Search Algorithms with Applications to the Secretary Problem

Cites work

• A 1.43-competitive online graph edge coloring algorithm in the random order arrival model
• A dynamic near-optimal algorithm for online linear programming
• A framework for the secretary problem on the intersection of matroids
• A Knapsack Secretary Problem with Applications
• A multiple-choice secretary algorithm with applications to online auctions
• A simple \(O(\log\log(\mathrm{rank}))\)-competitive algorithm for the matroid secretary problem
• Combinatorial secretary problems with ordinal information
• Dynamic Programming and Decision Theory
• scientific article; zbMATH DE number 718142 (Why is no real title available?)
• scientific article; zbMATH DE number 871933 (Why is no real title available?)
• scientific article; zbMATH DE number 3383344 (Why is no real title available?)
• Improved algorithms and analysis for secretary problems and generalizations
• Improved Online Algorithms for Knapsack and GAP in the Random Order Model
• Matroid Secretary Problems
• Matroids, secretary problems, and online mechanisms
• Online appointment scheduling in the random order model
• Online bipartite matching with random arrivals, an approach based on strongly factor-revealing LPs
• Primal beats dual on online packing LPs in the random-order model
• Revealing Optimal Thresholds for Generalized Secretary Problem via Continuous LP: Impacts on Online K-Item Auction and Bipartite K-Matching with Random Arrival Order
• Secretary Problems via Linear Programming
• Submodular secretary problems: cardinality, matching, and linear constraints
• The Secretary Problem and Its Extensions: A Review
• Who solved the secretary problem

Cited in

(10)

• Improved online algorithms for knapsack and GAP in the random order model
• Improved online algorithm for fractional knapsack in the random order model
• Online algorithms for the maximum \(k\)-interval coverage problem
• A new look at the returning secretary problem
• Improved algorithms and analysis for secretary problems and generalizations
• Uniformly bounded regret in the multisecretary problem
• scientific article; zbMATH DE number 7650251 (Why is no real title available?)
• Knapsack secretary through boosting
• The secretary problem with predictions
• A note on the satisficing policy of the secretary problem

This page was built for publication: New results for the \(k\)-secretary problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2658048)