Think Eternally: Improved Algorithms for the Temp Secretary Problem and Extensions

DOI10.4230/LIPICS.ESA.2016.54zbMATH Open1397.68232arXiv1606.06926OpenAlexW2964050979MaRDI QIDQ4606325FDOQ4606325

Andreas Tönnis, Thomas Kesselheim

Publication date: 2 March 2018

Abstract: The emph{Temp Secretary Problem} was recently introduced by Fiat et al. It is a generalization of the Secretary Problem, in which commitments are temporary for a fixed duration. We present a simple online algorithm with improved performance guarantees for cases already considered by Fiat et al. and give competitive ratios for new generalizations of the problem. In the classical setting, where candidates have identical contract durations $gammall1$ and we are allowed to hire up to $B$ candidates simultaneously, our algorithm is $(frac12-O(sqrtgamma))$-competitive. For large $B$, the bound improves to $1-Oleft(frac1sqrtBight)-O(sqrtgamma)$. Furthermore we generalize the problem from cardinality constraints towards general packing constraints. We achieve a competitive ratio of $1-Oleft(sqrtfrac(1+logd+logB)Bight)-O(sqrtgamma)$, where $d$ is the sparsity of the constraint matrix and $B$ is generalized to the capacity ratio of linear constraints. Additionally we extend the problem towards arbitrary hiring durations. Our algorithmic approach is a relaxation that aggregates all temporal constraints into a non-temporal constraint. Then we apply a linear scaling algorithm that, on every arrival, computes a tentative solution on the input that is known up to this point. This tentative solution uses the non-temporal, relaxed constraints scaled down linearly by the amount of time that has already passed.

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

zbMATH Keywords

online algorithmssecretary problemscheduling problems

Mathematics Subject Classification ID

Online algorithms; streaming algorithms (68W27) Analysis of algorithms and problem complexity (68Q25) Stopping times; optimal stopping problems; gambling theory (60G40)

Cited In (1)

• Know when to persist: deriving value from a stream buffer

This page was built for publication: Think Eternally: Improved Algorithms for the Temp Secretary Problem and Extensions

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