New results for the k-secretary problem

DOI10.1016/J.TCS.2021.02.022zbMATH Open1497.68576arXiv2012.00488OpenAlexW3131679123MaRDI QIDQ2658048FDOQ2658048

Authors: Susanne Albers, Leon Ladewig 

Publication date: 18 March 2021

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

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$.

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

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

zbMATH Keywords

online algorithmssecretary problemrandom order model

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (9)

• The secretary problem with predictions
• A new look at the returning secretary problem
• Improved online algorithms for knapsack and GAP in the random order model
• Improved algorithms and analysis for secretary problems and generalizations
• Title not available (Why is that?)
• Knapsack secretary through boosting
• Online algorithms for the maximum \(k\)-interval coverage problem
• Uniformly bounded regret in the multisecretary problem
• Improved online algorithm for fractional knapsack in the random order model

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)