A note on the online interval scheduling secretary problem

Bo Li, Chenhao Wang, Ruilong Zhang

Research output: Journal article publicationJournal articleAcademic researchpeer-review


The interval scheduling secretary problem models the scenario when a number of job intervals arrive randomly and the decider needs to assign some of them to machines irrevocably such that all assigned job intervals can be processed by machines without overlap, with the goal of maximizing the social welfare. Im and Wang ((2011) [7]) designed an almost optimal logarithm-competitive online algorithm for the single-machine case. In this note, we extend this result to multiple heterogeneous machines. Our algorithm preserves the competitive ratio and is thus nearly optimal.

Original languageEnglish
Pages (from-to)72-75
Number of pages4
JournalOperations Research Letters
Issue number1
Publication statusPublished - Jan 2022


  • Interval scheduling
  • Online algorithms
  • Secretary problem

ASJC Scopus subject areas

  • Software
  • Management Science and Operations Research
  • Industrial and Manufacturing Engineering
  • Applied Mathematics


Dive into the research topics of 'A note on the online interval scheduling secretary problem'. Together they form a unique fingerprint.

Cite this