A note on the online interval scheduling secretary problem
Research output: Journal Publications and Reviews (RGC: 21, 22, 62) › 21_Publication in refereed journal › peer-review
Author(s)
Related Research Unit(s)
Detail(s)
| Original language | English |
|---|---|
| Pages (from-to) | 72-75 |
| Journal / Publication | Operations Research Letters |
| Volume | 50 |
| Issue number | 1 |
| Online published | 16 Dec 2021 |
| Publication status | Published - Jan 2022 |
Link(s)
Abstract
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.
Research Area(s)
- Interval scheduling, Online algorithms, Secretary problem
Citation Format(s)
A note on the online interval scheduling secretary problem. / Li, Bo; Wang, Chenhao; Zhang, Ruilong.
In: Operations Research Letters, Vol. 50, No. 1, 01.2022, p. 72-75.
In: Operations Research Letters, Vol. 50, No. 1, 01.2022, p. 72-75.
Research output: Journal Publications and Reviews (RGC: 21, 22, 62) › 21_Publication in refereed journal › peer-review
