Kesselheim, Thomas ;
Tönnis, Andreas
Think Eternally: Improved Algorithms for the Temp Secretary Problem and Extensions
Abstract
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 nontemporal 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 nontemporal, relaxed constraints scaled down linearly by the amount of time that has already passed.
BibTeX  Entry
@InProceedings{kesselheim_et_al:LIPIcs:2016:6396,
author = {Thomas Kesselheim and Andreas T{\"o}nnis},
title = {{Think Eternally: Improved Algorithms for the Temp Secretary Problem and Extensions}},
booktitle = {24th Annual European Symposium on Algorithms (ESA 2016)},
pages = {54:154:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770156},
ISSN = {18688969},
year = {2016},
volume = {57},
editor = {Piotr Sankowski and Christos Zaroliagis},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2016/6396},
URN = {urn:nbn:de:0030drops63966},
doi = {10.4230/LIPIcs.ESA.2016.54},
annote = {Keywords: Secretary Problem, Online Algorithms, Scheduling Problems}
}
2016
Keywords: 

Secretary Problem, Online Algorithms, Scheduling Problems 
Seminar: 

24th Annual European Symposium on Algorithms (ESA 2016)

Issue date: 

2016 
Date of publication: 

2016 