Hiring Secretaries over Time: The Benefit of Concurrent Employment

Yann Disser (), John Fearnley (), Martin Gairing (), Oliver Göbel (), Max Klimm (), Daniel Schmand (), Alexander Skopalik () and Andreas Tönnis ()
Additional contact information
Yann Disser: Graduate School of Computational Engineering, Technical University of Darmstadt, Darmstadt 64293, Germany;
John Fearnley: Department of Computer Science, University of Liverpool, Liverpool L69 3BX, United Kingdom;
Martin Gairing: Department of Computer Science, University of Liverpool, Liverpool L69 3BX, United Kingdom;
Oliver Göbel: Department of Computer Science, RWTH Aachen University, Aachen 52062, Germany;
Max Klimm: School of Business and Economics, Humboldt University of Berlin, Berlin 10099, Germany;
Daniel Schmand: Department of Computer Science, Goethe University Frankfurt, Frankfurt am Main 60054, Germany;
Alexander Skopalik: Faculty of Electrical Engineering, Mathematics and Computer Science, University of Twente, Enschede 7500 AE, Netherlands;
Andreas Tönnis: Institute of Computer Science, University of Bonn, Bonn 53115, Germany

Mathematics of Operations Research, 2020, vol. 45, issue 1, 323–352

Abstract: We consider a stochastic online problem where n applicants arrive over time, one per time step. Upon the arrival of each applicant, their cost per time step is revealed, and we have to fix the duration of employment, starting immediately. This decision is irrevocable; that is, we can neither extend a contract nor dismiss a candidate once hired. In every time step, at least one candidate needs to be under contract, and our goal is to minimize the total hiring cost, which is the sum of the applicants’ costs multiplied with their respective employment durations. We provide a competitive online algorithm for the case that the applicants’ costs are drawn independently from a known distribution. Specifically, the algorithm achieves a competitive ratio of 2.965 for the case of uniform distributions. For this case, we give an analytical lower bound of 2 and a computational lower bound of 2.148. We then adapt our algorithm to stay competitive even in settings with one or more of the following restrictions: (i) at most two applicants can be hired concurrently; (ii) the distribution of the applicants’ costs is unknown; (iii) the total number n of time steps is unknown. On the other hand, we show that concurrent employment is a necessary feature of competitive algorithms by proving that no algorithm has a competitive ratio better than Ω ( n / l o g n ) if concurrent employment is forbidden.

Keywords: online algorithm; stopping problem; prophet inequality; Markov chain; secretary problem (search for similar items in EconPapers)
Date: 2020
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
https://doi.org/10.1287/moor.2019.0993 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormoor:v:45:y:2020:i:1:p:323-352

Access Statistics for this article

More articles in Mathematics of Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().