Scheduling in the Secretary Model

Susanne Albers, Maximilian Janke

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

1 Scopus citations

Abstract

This paper studies online makespan minimization in the secretary model. Jobs, specified by their processing times, are presented in a uniformly random order. The input size n is known in advance. An online algorithm has to non-preemptively assign each job permanently and irrevocably to one of m parallel and identical machines such that the expected time it takes to process them all, the makespan, is minimized. We give two deterministic algorithms. First, a straightforward adaptation of the semi-online strategy LightLoad [4] provides a very simple approach retaining its competitive ratio of 1.75. A new and sophisticated algorithm is 1.535-competitive. These competitive ratios are not only obtained in expectation but, in fact, for all but a very tiny fraction of job orders. Classically, online makespan minimization only considers the worst-case order. Here, no competitive ratio below 1.885 for deterministic algorithms and 1.581 using randomization is possible. The best randomized algorithm so far is 1.916-competitive. Our results show that classical worst-case orders are quite rare and pessimistic for many applications. We complement our results by providing first lower bounds. A competitive ratio obtained on nearly all possible job orders must be at least 1.257. This implies a lower bound of 1.043 for both deterministic and randomized algorithms in the general model.

Original languageEnglish
Title of host publication41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2021
EditorsMikolaj Bojanczyk, Chandra Chekuri
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (Electronic)9783959772150
DOIs
StatePublished - 1 Dec 2021
Event41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2021 - Virtual, Online
Duration: 15 Dec 202117 Dec 2021

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume213
ISSN (Print)1868-8969

Conference

Conference41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2021
CityVirtual, Online
Period15/12/2117/12/21

Keywords

  • Competitive analysis
  • Lower bound
  • Makespan minimization
  • Online algorithm
  • Random-order
  • Scheduling
  • Secretary problem

Fingerprint

Dive into the research topics of 'Scheduling in the Secretary Model'. Together they form a unique fingerprint.

Cite this