TU Darmstadt / ULB / TUbiblio

Hiring Secretaries over Time: The Benefit of Concurrent Employment

Disser, Yann ; Fearnley, John ; Gairing, Martin ; Göbel, Oliver ; Klimm, Max ; Schmand, Daniel ; Skopalik, Alexander ; Tönnis, Andreas (2020)
Hiring Secretaries over Time: The Benefit of Concurrent Employment.
In: Mathematics of Operations Research, 45 (1)
doi: 10.1287/moor.2019.0993
Artikel, Bibliographie

Kurzbeschreibung (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−−√/log  n) if concurrent employment is forbidden.

Typ des Eintrags: Artikel
Erschienen: 2020
Autor(en): Disser, Yann ; Fearnley, John ; Gairing, Martin ; Göbel, Oliver ; Klimm, Max ; Schmand, Daniel ; Skopalik, Alexander ; Tönnis, Andreas
Art des Eintrags: Bibliographie
Titel: Hiring Secretaries over Time: The Benefit of Concurrent Employment
Sprache: Englisch
Publikationsjahr: Februar 2020
Verlag: INFORMS
Titel der Zeitschrift, Zeitung oder Schriftenreihe: Mathematics of Operations Research
Jahrgang/Volume einer Zeitschrift: 45
(Heft-)Nummer: 1
DOI: 10.1287/moor.2019.0993
Kurzbeschreibung (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−−√/log  n) if concurrent employment is forbidden.

Fachbereich(e)/-gebiet(e): Exzellenzinitiative
Exzellenzinitiative > Graduiertenschulen
Exzellenzinitiative > Graduiertenschulen > Graduate School of Computational Engineering (CE)
Hinterlegungsdatum: 15 Jul 2022 07:40
Letzte Änderung: 30 Dez 2022 12:27
PPN: 503217980
Export:
Suche nach Titel in: TUfind oder in Google
Frage zum Eintrag Frage zum Eintrag

Optionen (nur für Redakteure)
Redaktionelle Details anzeigen Redaktionelle Details anzeigen