2026-08-18T01:28:13Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:6396 2024-03-06T10:38:10Z ddc:004 open_access

Think Eternally: Improved Algorithms for the Temp Secretary Problem and Extensions Kesselheim, Thomas Tönnis, Andreas Secretary Problem Online Algorithms Scheduling Problems The Temp Secretary Problem was recently introduced by [Fiat et al., ESA 2015]. 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., ESA 2015] and give competitive ratios for new generalizations of the problem. In the classical setting, where candidates have identical contract durations gamma << 1 and we are allowed to hire up to B candidates simultaneously, our algorithm is (1/2) - O(sqrt{gamma})-competitive. For large B, the bound improves to 1 - O(1/sqrt{B}) - O(sqrt{gamma}). Furthermore we generalize the problem from cardinality constraints towards general packing constraints. We achieve a competitive ratio of 1 - O(sqrt{(1+log(d) + log(B))/B}) - O(sqrt{gamma}), 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Thomas Kesselheim and Andreas Tönnis 2016 Is Part Of LIPIcs, Volume 57, 24th Annual European Symposium on Algorithms (ESA 2016) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2016.54 urn:nbn:de:0030-drops-63966 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2016.54 eng https://creativecommons.org/licenses/by/3.0/legalcode